4. Программное (теоретическое) кодирование и

ДЕКОДИРОВАНИЕ

Кодирование и декодирование циклическим кодом могут быть выполнены алгебраическими операциями (программный метод) либо в результате работы специально разработанных схем (схемный метод). При программном методе преобразование комбинаций, обнаружение и исправление ошибок производятся алгебраическими операциями над многочленами, для выполнения которых программируется вычислительная система устройств связи. Особенностью алгебраических действий в теории кодирования является замена операций сложения и вычитания одной – сложением по модулю два. При этом четное число одинаковых членов дает ноль, а нечетное – единицу. Поэтому, например, х х = 0; х х х = х (знак означает сложение по модулю два). Поскольку заданием предполагается выполнение только алгебраических операций без составления программы, назовем этот способ теоретическим. Теоретическое кодирование в свою очередь может быть выполнено двумя способами:

умножением k-элементной комбинации простого кода на образующий полином g(x) (в результате получают комбинацию неразделимого циклическо-го кода);

умножением кодовой комбинации простого кода на одночлен х^r и добавлением к этому произведению остатка от деления произведения х^r P(x) на g(x). В результате получают комбинацию разделимого циклического кода.

Неразделимость кода значительно усложняет процесс декодирования, поэтому на практике чаще используется второй способ построения кодовых комбинаций.

Пример. Пусть 1100 (k = 4) – последовательность информационных символов, тогда соответствующий ей полином сообщения P(x) = x³ + x².

Требуется определить n-элементную кодовую комбинацию разделимого циклического кода, если известен образующий полином: g(x) = x³ + x +1.

Общее число элементов избыточной кодовой комбинации n = k + r = 7.

Остаток от деления произведения х^r P(x) на g(x) равен x, поэтому полином разделимого циклического кода F(x) = x⁶ + x⁵ + x, а комбинация имеет вид: 1100010. В этой комбинации четыре старших разряда соответствуют исходной комбинации, а три младших являются проверочными. Для тех же условий комбинация неразделимого циклического кода имеет вид: 1110100, в ней выделить информационную и проверочную части нельзя.

Посылки кодовой комбинации F(x) отправляются в канал связи, начиная с высшего разряда.

Одним из свойств циклического кода является деление разрешенной кодовой комбинации на образующий полином без остатка. Следовательно, появление остатка от деления говорит о наличии ошибки. В кодах, работающих в режиме исправления ошибок, вид остатка однозначно определяет порядковые номера ошибочных разрядов. Поэтому для декодирования предварительно следует составить таблицу синдромов ошибок (остатков от деления) для всех вариантов ошибочных разрядов. Повторение синдромов в этой таблице означает невозможность исправления, так как появляется неопределенность, и это соответствует режиму обнаружения ошибок.

Для циклических кодов, как и для любых систематических кодов, нулевая комбинация является разрешенной, например, для кода с n = 7, k = 4 и r = 3 эта комбинация имеет вид: 0000000. Поэтому таблицу синдромов ошибок проще всего составить на примере именно такой комбинации, поочередно перебирая в ней ошибочные разряды. Для рассматриваемого примера комбинация 1000000 (х⁶) содержит однократную ошибку (в первом разряде), а комбинация 0100100 (х⁵ + х²) – двукратную (во втором и пятом разрядах). В этом примере учтено, что при d₀ = 3 разрешенные комбинации должны отличаться по крайней мере на три разряда.

В конце данного раздела следует выполнить декодирование двух комбинаций: разрешенной, полученной при теоретическом кодировании, и ошибочной (с введением ошибки в заданный разряд, см. табл. 3).