Главная > Помехоустойчивое кодирование > Коды, исправляющие ошибки
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

8.5. Кодирование с помощью регистра сдвига, содержащего n - k разрядов

Кодовое слово может быть найдено как результат умножения многочлена степени к — 1 или меньше, коэффициентами которого являются произвольные информационные символы, на порождающий многочлен кода. Умножение можно осуществить, используя линейную схему, изображенную на рис. 7.2, или линейную схему, изображенную на рис. 7.3. При таком методе кодирования информационные символы появляются в кодовом многочлене в измененном виде, однако они могут быть восстановлены по неискаженному кодовому многочлену путем деления его на многочлен Для деления можно использовать схему, изображенную на рис. 7.6.

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

Любой циклический код может быть получен в таком виде в результате выполнения следующего процесса, Пусть многочлен, в качестве коэффициентов которого при слагаемых, содержащих выбраны произвольные информационные символы, а коэффициенты при слагаемых, содержащих степени X, меньшие, чем равны 0. Этому многочлену соответствует вектор, первые компонент которого равны 0, а последние к компонент-произвольные информационные символы. Тогда, в соответствии с алгоритмом деления Евклида [соотношение (6.4)]

где степень многочлена меньше, чем степень многочлена Отсюда

и, следовательно, кодовый вектор. Так как степень меньше, чем то все слагаемые в этом многочлене

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

Остается задача найти способ вычисления остатка от деления многочлена на Это можно сделать, используя схему для деления, изображенную на рис. 7.6. Многочлен коэффициенты которого при членах высших порядков задаются информационными символами, а коэффициенты при к членах низших порядков равны 0, будем подавать в схему, начиная с коэффициентов высших разрядов, до тех пор, пока его последний коэффициент не попадет в младший разряд регистра сдвига. Для этого потребуется всего сдвигов, для информационных символов и для нулей в младших разрядах. В результате в регистре сдвига останется остаток от деления коэффициенты которого только знаком будут отличаться от проверочных символов. Полученными проверочными символами можно затем заменить символы младших разрядов в векторе с тем чтобы образовать кодовый вектор.

Рис. 8.2. Кодирующее устройство с предварительным автоматическим умножением на

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

1. k информационных символов поступают в устройство, изображенное на рис. 8.2, и одновременно в канал связи. Как только все информационных символов поступят в регистр сдвига, совокупность символов, находящихся в этот момент в разрядах регистра сдвига, совпадает с остатком, т. е. с совокупностью проверочных символов, взятых с обратным знаком.

2. В регистре сдвига прерывается линия обратной связи, напри» мер, с помощью клапана, помещенного в точке, показанной на схеме.

3. Производятся сдвиги содержимого регистра; у символов, появляющихся на выходе, знак изменяется на обратный, после чего они подаются в канал связи. Эти проверочных символов вместе с информационными символами образуют кодовый вектор.

Полученный вектор можно проверить при помощи проверок на четность, просто подав его на вход схемы, изображенной на рис. 7.6, или на вход схемы, изображенной на рис. 8,2, в регистры которых предварительно занесены нули. После того как вектор введен, содержимое регистра сдвига должно совпадать с остатком от деления соответствующего многочлена на следовательно, будет нулевым вектором тогда и только тогда, когда введенный вектор был кодовым.

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

Пример. На рис. 8.3 для двоичного циклического -кода с показано устройство, эквивалентное устройству, изображенному на рис. 8.2.

Рис. 8.3. Кодирующее устройство, содержащее к разрядов для циклического -кода.

Кроме того, кодирование можно производить этим же методом, но используя схемы, полученные из основных схем для деления, преобразованием последних, описываемым соотношениями (7.30). Для схемы, изображенной на рис. 8.2, это преобразование можно сделать в обоих случаях: для открытого клапана и для закрытого клапана, так чтобы получить правильные соединения в каждом из этих случаев.

Пример. Матрицы для схемы на рис. 8.3 при закрытом клапане

и при открытом клапане

Если преобразование, задаваемое матрицами

применить к этой цепи, то при закрытом клапане -0 0 1-

а при открытом клапане

Получающаяся в результате схема показана на рис. 8.4.

Рис. 8.4. Схема, эквивалентная схеме, изображенной на рис. 8,3.

<< Предыдущий параграф Следующий параграф >>
Оглавление