У. Питерсон - Коды, исправляющие ошибки (1267328), страница 52
Текст из файла (страница 52)
В последней упомянутой работе авторы доказали существование бесконечного, но очень разреженного класса кодов, минимальные расстояния которых несколько больше, чем минимальные расстояния соответствующих БЧХ-кодов. 87. Методы кодирования Очень простые методы кодирования циклических кодов, описанные в этом разделе, используются для иллюстрации одной из наиболее важных особенностей циклических кодов †легкос их реализации. В обоих рассматриваемых здесь методах предполагается, что из источника поступают блоки из й информационных символов, которые затем без задержки попадают в канал. После этого посылаются следующие за каждым таким блоком и — й проверочных символов; в течение этого времени никакая информация из источника принята быть не может. Таким образом, в обоих методах декодирования предполагается наличие источника, способного по команде начинать и прекращать выдачу символов, или же использование буферного устройства.
Ниже описываются два способа сопоставления информационному набору из й символов кодового слова циклического кода. При первом способе используется регистр сдвига с й ячейками, при втором — регистр сдвига с и — А ячейками. Для кодов, число проверочных символов в которых больше числа информационных символов, вообще говоря, предпочтительнее первый способ, тогда как для кодов, в которых Цп) 0,5, второй способ оказывается обычно более экономичным.
Оба способа порождают одни и те же кодовые слова. Кодирование для циклического (п,й)-кода, порожденного многочленом д(Х) степени п — й, может быть произведено с помощью регистра сдвига с й ячейками (фиг. 7.14), соединения в котором соответствуют многочлену й(Х) =(Х" — 1)/д(Х). Сначала информационные символы помещаются в эти Й ячеек, затем производится и сдвигов. Первые й символов, появившихся на выходе, будут информационными, а последние п — й символов — проверочными. Вместе они образуют кодовый вектор длины и.
То, что это действительно так, следует из теоремы 7.1. 17рилегр. Для двоичного (7,4)-кода Хэммннга, рассмотренного в предыдущем примере, д(Х) = Ха+ Х+1, а й(Х) = (Х'+ +1)/д(Х) = Ха+ Ха+ Х+1. Для кодирования может быть использован регистр сдвига, изображенный на фиг.
8.1. В результате четырех сдвигов четыре заданных символа будут помещены в ячейки регистра. Поскольку входы двоичного сумматора соответствуют ненулевым членам й(Х) (см. задачу 8.9), то на его выходе появится первый проверочный символ. В результате пятого сдвига этот символ вводится в самый правый разряд регистра, а иа выходе появляется первый информационный символ.
Далее, в силу цикличности кода второй проверочный символ является Выхад Фиг. 8.1. Регистр сдвига с й ячейками для иодироиания (7,4)-иода, порожденного многочленом Л' + Х + 1. суммой символов, расположенных относительно друг друга в тех же разрядах, как и в случае первого проверочного символа. Следовательно, выход сумматора равен этому второму проверочному символу. Третий проверочный символ вычисляется аналогичным образом.
Теперь рассмотрим кодирование при помощи регистра сдвига с и — й ячейками. Кодовое слово может быть найдено как результат умножения многочлена степени й — 1 или меньше, коэффициентами которого являются произвольные информационные символы, на й(Х) — порождающий многочлен кода.
Умножение можно осуществить, используя линейную схему, изображенную на фиг.7.2, или схему, представленную на фиг. 7.3. При таком методе кодирования информационные символы появляются в кодовом много- члене в измененном виде, однако они могут быть восстановлены по неискаженному кодовому многочлеиу путем деления его на многочлен д(Х). Для деления можно использовать схему, изображенную на фиг. 7.6.
В большинстве случаев значительно удобнее, чтобы кодовый вектор состоял из й неизмененных информационных символов, за которыми следуют п — й проверочных символов, т. е. удобнее иметь систематический код. Любой циклический код может быть представлен в таком виде при помощи приведенного ниже построения. Пусть ~а(Х) — многочлен, в качестве А коэффициентов которого при слагаемых, содержащих Х" — ', Х вЂ” з, ..., Х" ", выбраны произвольные информационные символы, а коэффициенты при слагаемых со степенями Х, меньшими чем и — й, равны О. Этому многочлену соответствует вектор, первые й компонент которого— произвольные информационные символы, а последние п — й компонент равны О. Тогда в соответствии с алгоритмом деления Евклида [соотношение (6.4)] 1а(Х) = д(Х) <у(Х)+ г(Х), где степень мвогочлеиа г(Х) меньше чем и — й, степень много- члена д(Х).
Отсюда Р (Х) — г(Х) =д(Х) д(Х), н, следовательно, Ц>(Х) — г(Х)] — кодовый вектор. Так как степень г(Х) меньше чем и — й, то все слагаемые в этом миогочлене степени п — й илн больше равны О. Следовательно, коэффициентами при членах высшего порядка в многочлене )а(Х) — г(Х) являются неизменные информационные символы, а коэффициентами при членах низшего порядка (коэффициентами многочлена — г(Х)] — неизмененные проверочные символы. Получаемый таким комбинированием кодовый вектор ничем не отличается от кодового вектора, получаемого при помощи регистра сдвига, содержа- Фиг. 8лп Кодер с автоматическим предварительным умножением на х" щего й ячеек, если в обоих случаях выбраны одни и те же информационные символы. Остается задача вычисления остатка от деления многочлена ге(Х) иа д(Х).
Это можно сделать, используя схему деления, изображенную на фиг. 7.6. Многочлен (е(Х), коэффициенты которого при А членах высших порядков задаются информационными символами, а коэффициенты при а — Й членах низших порядков равны О, будем подавать в схему начиная с коэффициентов высших разрядов до тех пор, пока последний коэффициент не попадет в ячейку младшего разряда регистра сдвига.
Для этого потребуется всего л сдвигов: й для информационных символов и и — й для нулей в ячейках младшего разряда. В результате в регистре сдвига останется остаток от деления г(Х), коэффициенты которого только знаком будут отличаться от проверочных символов. Полученными проверочными символами можно затем заменить символы и — й младших разрядов в векторе Да(Х)) с тем, чтобы образовать кодовый вектор. Этот процесс может быть сделан более прямолинейным, если ввести в схему видоизменения, показанные на фиг. 8.2. Эти видоизменения приводят к тому, что, как только символ поступает в регистр сдвига, производится автоматическое умножение его на Х -а. При этом кодирование производится следующим образом: 1.
и информационных символов поступают в устройство, изображенное на фиг. 8.2, и одновременно в канал связи. Как только все й информационных символов поступят в регистр сдвига, совокупность а — А символов, находящихся в этот момент в регистре сдвига, совпадает с остатком, т. е. с совокупностью проверочных символов, взятых с обратным знаком. 2. В регистре сдвига выключается линия обратной связи, например с помощью ключа.
Выход Влад Фиг. 8.8. Кодер с а — я ячейками дан циклического (у, 4)-кцца, порожденнега многсчленом Х'+ Х+ 1. ВХОд — в фиг. 8.4. Схема, аивиаааентная схеме, изображенной на фиг. 8.8. 3. Производятся сдвиги содержимого регистра; у символов, появляющихся иа выходе, знак изменяется на обратный, после чего они подаются в канал связи. Эти и — й проверочных символов вместе с й информационными символами образуют кодовый вектор. Пример. На фиг. 83 для двоичного циклического (7,4)-кода Хэммипга с д(Х) = Х'+Х+1 показано устройство, эквивалентное устройству, изображенному иа фиг. 8.2. Кроме того, кодирование можно производить прн помощи некоторой модификации описанного метода, используя схемы, полученные из основной схемы деления преобразованием, описываемым соотношениями (7.30).
Для схемы„изображенной на фиг. 8.2, это преобразование можно сделать как при открытом, так н при закрытом ключе. В каждом из этих случаев должны быть получены правильные соединения. Пример. Матрица для схемы иа фиг. 8.3 при закрытом ключе имеет вид 010 Т = 0 0 1 , 1) = (1 1 0], 1( = [0 0 11, 8 = (11, 110 а прн открытом ключе 11 = 10001, мг=(00 Ц, 8=11). Т= 001 Если преобразование, задаваемое матрицами А= 110, А '= 011 применить к этой схеме, то при закрытом ключе получим оо( Т'= ( О(, ()'=(0ОЦ, К' =(( ) 01, 8'=(() о(о а при открытом ключе ооо Т'= (ОО, Г=(0О0), К'=(((О], 8 =Щ. 0(О Получающаяся в результате схема показана на фиг. 8.4 8.8. Обнаружение ошибок с помощью циклических кодов Циклические коды хорошо приспособлены для целей обнаружения ошибок, ибо эти колы всегда могут быть сконструированы так, чтобы.они могли обнаруживать многие наиболее правдоподобные комбинации ошибок, и для этих кодов практически реализуемы операции кодировацня и обнаружения ошибок.
Обычно при обнаружении ошибок число проверочных символов меньше числа информационных символов. Поэтому кодирование лучше осуществлять, используя регистр сдвига с числом ячеек, равным числу проверочных символов в коде. (См. равд. 8.7.) То же самое устройство может быть использовано длн обнаружения ошибок в проверочных символах. Для этого достаточно вычесть полученные проверочные символы из проверочных символов, вычисленных на приемнике (или в двоичном случае сложить эти символы).
Если в результате получится пуль, то полученное слово является кодовым словом; в противном случае это ие так. В двоичном случае это сложение производится автоматически при помощи схемы, изображенной иа фиг. 8.2; таким образом, достаточно только определить, состоит ли набор длины (и — й) на выходе целиком из нулей или нет. Теперь проанализируем возможности обнаружения ошибок. Теорема 8.5. Ни один из векторов циклического (п,А)- кода не является пакетом длины и — й или меньше. Следовательно, любой циклический (и, й)-код может обнаруживать любой пакет ошибок длины и — й или меньше. Доказательство, Пусть (г(Х)) — пакет длины и — й или меньше, и предположим, что код, о котором идет речь, порожден многочленом д(Х) степени и — й.
Допустим, что первым отличным от нуля коэффициентом в мпогочлене г(Х) является коэффициент при Х'. Тогда г(Х) =Х~гр(Х), где степень многочлена гь(Х) меньше чем п — й, так как [г(Х))— пакет длины, не превосходящей и — А. Многочлен Х" — 1 делится на и(Х), поэтому многочлен д(Х) ие может делиться на Х и, следовательно, многочлены Х' и д(Х) взаимно просты. Итак, если многочлен г(Х) делится на д(Х), то и многочлен гь(Х) должен делиться на д(Х), что невозможно, так как степень многочлена и(Х) больше степени гь(Х), Следователыю, вектор (г(Х)) не мо-.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
