Калмыков В.В. Радиотехнические системы передачи информации (1990) (1151851), страница 18
Текст из файла (страница 18)
Им может быть любой многочлен р(х) степени и — й, который делит без остатка дву член х"В1. Циклические коды характеризуются тем, что многочлены Ь(х) кодовых комбинаций делятся без остатка на р(х). Поэтому процесс кодирования сводится к отысканию многочлеиа Ь(х) по известным многочленам а(х) и р(х), делящегося на р(х), где а(х) — многочлен степени й — 1, соответствующий информационной последовательности символов. Очевидно, что в качестве многочлена Ь(х) можно использовать произведение а(х) р(х). Однако при этом информационные и проверочные символы оказываются перемешанными, что затрудняет процесс декодирования. Поэтому па практике в основном применяется следующий метод нахождения многочлена Ь(х).
Умножим многочлен а(х) на х -" и полученное произведение разделим на р(х). Пусть а(х)х"-а=т(х) р(х) Вс(х), (7.12) где т(х) — частное, а с(х) — остаток. Так как операции суммирования и вычитания по модулю 2 совпадают, то выражепие (7.12) перепишем в виде а(х)х™Вс(х) =т(х) р(х). (7.13) Из (7.13) следует, что многочлен а(х)х" — "Вс(х) делится на р(х) и, следовательно, является искомым. Многочлен а(х)х а имеет следующую структуру: первые и — й членов низшего порядка равны нулю, а коэффициенты остальных совпадают с соответствующими коэффициентами информационного многочлена а(х).
Многочлен с(х) имеет степень меньше и — й. Таким образом, в найденном мяогочлене Ь(х) коэффи- Рнс. 7.3. Схемы умножения (о) и деления (о) многочленов (частный случай) Рис. 7Д. Структурная схема кодера циклического кода, вадаваемого проверочным многочлеиом Ь(х) = — х4ЕХЗЕД2Е1 Рис. 7.4 Структурная схема кодера циклического кода с порождающим мноточлеиом р(х) =. лчвхеЮ! 159 „,,:-": цнснты при х в степени и — й и выше совпадают с информационными символами, а коэффициенты при остальных членах, определяемых многочленом с(х), совпадают с проверочными симшышми В соответствии с (7.13) процесс кодирования заключается в умножении многочлеиа а(х) па х -" и нахождении остатка от деления а(х)хв-" на р(х) с последующим его сложением по модулю 2 с многочленом а(х)хо-".
Операции умножения и деления многочленов легко осуществляются линейными цепями па основе сдвигающих регистров (19). В качестве примера на рис. 7.3,а представлена схема умножения мпогочлена Ь(х) степени и=б на многочлен )(х) =х'ВхВ1 по модулю х'В1. Нетрудно убедиться, что после семи тактов в регистре записывается многочлен Ь(х)((х)глоб(хтВ1). При делении миогочлена Ь(х) степени и=6 на многочлеи )(х) =хвВхвВ! (рис.
7.3,6) после семи тактов в регистре оказываетоя записант иым остаток от деления. На основе приведенных схем умножения и деления многочлеаов и строятся кодирующие устройства для циклических кодов. На рис. 7.4 и качестве примера приведена схема кодера для ыода (7,4) с порождающим многочлеиом р(х) =х'ВхеВ1. В исходном состоянии ключи К, и Кя находятся в положении !. Информационные символы поступают одновременно на вход канала и на выход ячейки хв сдвигающего регистра (это соответству- ст умножению многочлена а(х) на х'), В тсчение четырех тактов происходит деление многочлена а(х)х2 на многочлен р(х) = =х'ЮхеВ!.
В результате в регистре записывается остаток, представляющий собой проверочные символы. Ключи К, и К, перебрасываются в положение 2, и в течение трех послсдукпцих тактов содержащиеся в регистре символы поступают в канал. Циклический код может быть задан проверочнылч многочленом Ь(х): кодовая комбинация В принадлежит данному циклическому коду, если Ь(х) Ь(х) =Отой(х"Ю!). Проверочный мпогочлен связан с порождающим соотношением Ь(х) = (л"В1)Л~(х) Задание кода проверочным мпогочленом эквивалентно заданию кода системой проверочных уравнений (7.11).
Характерной особенностью циклического кода является то, по все проверочные уравнения можно получить из одного путем циклического сдвига индексов символов, входящих в исходное уравнение. Так, для кола (7,4) с порождающим многочлепом р(х) =хзЮх'Ю1 проверочный многочлен имеет вид Ь(х) =х'Вх'Вх'Ю1. Проверочные уравнения получаются из условия Ь(х) Ь(х) =Отой(хгЮ1).
Осуществив умножение и приравняв коэффициенты при х', х' и хе нулю, получим следующие уравнения, разрешенные относительно проверочных символов; Ь2 ЬЬВЬ2ЮЬЗ Ь2=62ЮЬ2ЮЬ2, (7.14) Ьд=Ь ВЬ2ВЬь В качестве примера на рис. 7.5 показана схема кодера циклического кода (7,4), задаваемого проверочным многочленом Ь(х) = =х'Юх'Юх'Ю1 или, что то же самое, проверочными соотношениями (7.14). В исходном состоянии ключ находится в положении 1.
В течение четырех тактов импульсы поступают в регистр, после чего ключ переводится в положение 2. Пря этом обратная связь замыкаетея. Начиная с пятого такта, формируются проверочные символы в соответствии с (7.14). После седьмого такта все проверочные символы оказываются сформированными, ключ вновь переключается в положение 1. Кодер готов к приему очередиого сообщения.
Символы кодовой комбинации поступают в канал, начиная с питого такта. Корректирующая способность кода зависит от порождаюгцего многочлена р(х). Поэтому его выбор очень важен при построении циклического кода. Необходимо помнить, что степень порожлающего многочлена должна быть равна числу проверочных символов. Кроме того, многочлеп р(х) должен делить двучлен х"Ю1. Обнаружение ошибок при использовании таких кодов заключается в делении многочлена б(х) =Ь(х)+е(х), соответству7юще- 160 го рипятой комбинации Я=ВЮе„на р(х). Если остаток з(х) оказывается равным нулю, то считается, что ошибки нет, в про- тивном случае фиксируется ошибка.
Пусть..необходимо..2юстроях .код,-обнаруживлкнццй все оди- ночные ошибки. В этом случае многочлен ошибок е(х) =х', где 2= О, 1, ..., и — 1. Решение задачи заключается в нахождении та- кого многочлена р(х), чтобы многочлен е(х) не делился на р(х). 1!анболее простым удовлетворяющим этому требованию является мпогочлен р(х) =хЮ!. Лпалогично можно построить код, обнаруживающий ошибки большей кратности Многочлеп з (х) =- 1Ь (х) Ве (х) ] той р (х) = е (х) пюй р (х) зависит только от многочлена ошибок е(х) и играет ту же роль, по и вектор — синдром. Поэтому в принципе ошибки можно ис- правлять на основе таблицы соответстний между е(х) и з(х), хра- нящейся в памяти декодера, как при линейных пециклических ко- лах. Однако свойство цикличности позволяет существенно упро- стить йроцедуру деколирования Одни из алгоритмов исправления ошибок основан на следую.
шнх свойствам синдрома циклического кода. Пусть имеется цик- лический код с кодовым расстоянием 21, исправляющий все ошиб- ки ло кратности ! =- ~ — ~ включительно, где [(г( — 1)/2] — целая 2 часть числа (21 — 1)/2. Тогда можно показать (19, 25], что если исправляемый вектор ошибок искажает только проверо,- ныс символы, то вес синдрома будет меньше нли равен 1, а сам синдром будет совпадать с вектором ошибок, если вектор оп!нбкн искажает хотя бы один информационный символ, то вес синдрома будет больше 1: если з(х) — остаток от деления многочлена Ь(х) па р(х), то остатком от деления многочлепа Ь(х)х' па р(х) является мио- гочлен з(х)хчпойр(х), другими словами, синдром некоторого ци- клического сдвига многочлена Ь(х) является соответствующим циклическим сдвигом синдрома исходного многочлена, взятого по модулю р(х).
В качестве примера иа рпс. 7.6 представлена схема декодера Лля кода (7, 4) с порождаюшпм мпогочленом р(л) =х'Вх'Ю1. Кол имеет кодовое расстояние г1=3, что позволяет ему исправ- лять все однократные ошибки. Принятая кодовая комбинация одновременно поступает в бу- ферный регистр сдвига, служащий для запоминания кодовой ком- бинации и для ее циклического сдвига, и на устройство деления на мпогочлен р(х) для вычисления синдрома. В исхолпом состоянии ключ находится в положении 1. После семи тактов буфсрный ре- гистр оказывается загруженным, а в регистре устройства деления будет вычислен синдром.
Если вес синдрома больше единицы, то декодер начинает производить циклические сдвиги комбинации в 6-- 9 !61 Рве, 7.6. Структурная схема декодера циклпческого кода с порождающим мно- гочленом р(х) =хзчтхЧЬ! буферном регистре при отсутствии новой комбинации на входе н одновременно вычислять их синдромы з(х)хзгподр(х) в устрой- стве деления. Если на некотором г-м шаге вес синдрома окажет- ся меньше 2, то ключ переходит в положение 2, обратные связи т:," в регистре деления разрываются. При последующих тактах ошиб- ки исправляются путем подачи содержимого регистра деления на вход сумматора по модулю 2, включенного в буферный регистр. После семи тактов работы декодера в автономном режиме ис- правленная комбинация в буферном регистре возвращается в ис- ходное положение (информационные символы будут занимать старшие разряды).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
