CRC коды
Вопрос не то чтобы по программированию, но надеюсь мне здесь помогут.
Допустим нам надо закодировать сообщение длиной 24 бита - для этого мы
по всем правилам сначало сдвигаем вправо на k разрядов, где k - степень нашего полинома, делим на полином и прибавляем остаток к сдвинутому сообщению, ну а потом все это посылаем. На принимающей стороне происходит декодирование сообщения и проверка его целостности. По алгоритму я могу найти и исправить одну ошибку в своем принятом коде, соответсвенно если ошибки 2 то их уже исправить нельзя. Вопрос - как определить что в принятом сообщении больше одной ошибки? По алгоритму я должен сдвигать влево, делить и проверять вес остатка, когда он равен числу исправляемых бит, то делаем сумму по модулю 2 со сдвинутым сообщением и сдвигаем все это влево на нужное число разрядов. На сколько я понимаю если ошибок более одной, то такой ситуации не возникнет (когда вес остатка <= числу исправляемых бит), но она возникает. Я пишу программу которая кодирует сообщение CRC кодом и для тестов вношу ошибку в закодированное сообщение ( в более чем 2-х битах), но все равно получаю случай, когда когда вес остатка <= числу исправляемых бит. Как точно определить что принятое сообщение содержит более одной ошибки?
так вот собственно и ответ - если исправление не дает результат, значит тама 2 и более ошибок (те более одной)...
PS Рекомендую почитать книгу - "Коды контролирующие ошибки" особ что касается кодов Хэминга (сейчас она помоему на работе, если что, кто и когда написал отпишу позже, я сегодня дома)...
вот здесь мне немного непонятно - "если исправление не дает результат" - я передаю данные по сети - и не могу наверняка знать, исправил ли я все ошибки, или я что-то не так понимаю?
Вопрос - как Вы определяете что ошибка исправлена... Пересчитав CRC? И какое соотношение длин СRC и самого передаваемого кода?
Вообщето для исправления ошибок применяются несколько другие алгоритмы, хотя их конечно можно причислить к CRC, но если вдаваться в подробности это не совсем то. А именно применяется "увеличение" передаваемого кода с добавлением в него к примеру кодов Хэминга (на заре развития ЭВМ) или циклических Синглтона и Рейгера кодов для исправления большего количества ошибок, при этом их размер расчитывается из требования исправления конкретного количества ошибок, или ипользуется избыточность для повторения "вшитых" предыдущих блоков данных сдвинутых по времени (для радиоканалов как правило)...
А зачем вообще это Вам нужно, если вы передаете данные по сети, там на "низу" и так все это делается на аппаратном уровне, и очень даже качественно, так что передача с гарантией...
PS Р.Блейхут "Теория и практика кодов, контролирующих ошибки." (Покупал когда занимался ракетно-ядерной телеметрией, ох уж их там... ошибок и сбоев, но все решаемо как оказалось)
Сдвигаем 24 инф.бита влево на 5 разрядов, делим это на выбранный полином(P(x)) и остаток складываем со сдвинутыми битами, и все это дело посылаем по сети.По условию такой код позволяет обнаружить и исправить 1 ошибку (s = 1).
Алгоритм исправления я использую такой -
1.Полученный код делим на полином P(x)(который использовался для шифрования) - если остаток равен 0, значит ошибок нет. Если не равен, то считаем вес (w) остатка (количество единиц) - если w<=s, то складываем по модулю 2 полученный код и остаток и по алгоритму это будет 100% исправленный код.
2. Если w>s то полученный код сдвигают влево на 1 и переходим к пункту 1. В конце полученный код сдвигают вправо на количество сдвигов влево.
На сколько я представляю, если ошибок >1, то сколько бы мы не сдвигали влево, мы никогда не получим случая w<=s.Но проблема в том, что это не так. Даже если в принятом коде больше одной ошибки, все равно мы получаем случай когда w<=s и соотвественно исправляем ошибку, но их-то >1. Т.е. как определить, что в принятом коде больше одной ошибки?
А зачем вообще это Вам нужно, если вы передаете данные по сети там на "низу" и так все это делается на аппаратном уровне, и очень даже качественно, так что передача с гарантией...
лаба такая, тут ничего не сделаешь.. :)
Допустим на принимающей строне мы получили некий код. Сколько в нем ошибок (и есть ли вообще) мы не знаем. Все что у нас для этого есть - полином. Работу своей программы я тестировал так - преобразую заданную комбинацию в код, затем намеренно делаю там, например, 2 ошибки. Принимающая функция об этом ничего не знает. Ей надо понять, что если ошибок больше, чем она сможет наверняка исправить (в данном случае больше одной), то следовательно надо послать отрицательную квитанцию для передатчика, чтобы он повторил передачу кода. Так вот, когда функция принимает заведомо с 2-мя ошибками код, то одну она находит всегда, но во-первых не в том месте, а во вторых их там две. Таким образом функция думает что нашла ошибку и восстановила код, но на самом деле это не так, функция каким-то образом должна была определить, что ошибок более одной(и восстановить код она уже никак не сможет) и послать запрос на повторную передачу.
На том сайте алгоритм идентичный, там те же сдвиги влево, только иной способ определения и исправления бита с ошибкой.
P.S. Книгу в элктронке скачал, читаю нужный раздел, но если честно книжка конечно тяжеловатая, но надеюсь разберусь.
Так что мне кажется что при данном конкретном случае такие преобразования ничего особо не дадут.
PS кроме теории там есть главы по схемотехническому построению, что более понятно на мой взгляд...
А вот циклические коды на подобии кода Рида Соломона уже позволяют проводить и непосредственные исправления.
Рекомендую статью к прочтению: "Могущество кодов Рида-Соломона или информация, воскресшая из пепла"
Правда стиль статьи немного тяжеловат, но дает общее представление о применении кодов.