Вернер М. Основы кодирования (2004) (1151882), страница 25
Текст из файла (страница 25)
3.6. Схема деления многочленов /(х)а(х)д(х) + Ь(х).: д(х) —На последующих I = т — г тактах алгоритм деления остаетсятаким же. Так, если степень укороченного многочлена f(X) в (3.60),Глава 3. Циклические кодыравная к\ (3.61), остается большей и равной г, то с помощью цени обратной связи производится укорочение теперь уже многочлена f(X)из (3.60).f{X) = f(X)(3.62)= f(X)со степенью(3.63)-к2<ку.Таким образом, после I = т — г тактов мы получаем разложение(3.59), причем, в регистре делимого находится остаток от деленияЬ{Х). После этого, ключ 51 размыкается, переключатель 52 переводится в нижнее положение и на следующих г тактах остаток Ь(Х)заносится в регистр формирователя остатка.Как уже упоминалось ранее, кодер систематического кода не использует при своей работе сомножитель а(Х) из разложения (3.59).Его задачей является только получение остатка от деления сдвига информационного многочлена на порождающий многочлен д(Х).Этот остаток образует затем младшие разряды кодового слова.Тактп01тТТТЛИШ345fiX)10010'()гп||ft,>]110111 0Г1I1!1Остаток01001Рис.
3.7. Схема деления многочлена 1 + X + X2 + X4 на1 + Х2.В связи с вышеизложенным, схему деления двух многочленов(рис. 3.6) для нужд кодирования можно существенно упростить. Заметим, что для получения остатка от деления по алгоритму Евклида,нам достаточно хранить в памяти помимо делимого только промежуточные суммы. Если степень д(Х) равна г, каждая промежуточнаясумма занимает не более чем г двоичных разрядов и обновляется накаждом такте процедуры деления, причем, на этом же такте производится сложение очередного двоичного разряда промежуточнойсуммы с соответствующим разрядом делимого. Таким образом, схема деления многочлена f(X) = 1 + X + X2 + X4 на д{Х) = 1 + X23.5. Схемная реализация циклического кодирования• * .(рис. 3.5) преобразуется в схему получения остатка от деления (рис.3.7).
Здесь уже не требуется предварительной загрузки делимого врегистр деления, а остаток bo, b\ образуется в этом регистре на пятомтакте.Выше мы подробно разобрали схемные реализации алгоритмовделения Евклида. Покажем теперь принцип действия схем кодирования циклических кодов, построенных на регистрах сдвига с обратными связями. Рассмотрим уже знакомый нам систематический кодХэмминга с порождающим многочленом д(Х) = 1 + X+ X3 (3.24).Пусть передается информационный вектор и = (1001) из (3.30). Согласно (3.35), ему соответствует кодовое слово в систематическомвиде v = (011 1001). Алгоритм деления Евклида для вычисленияпроверочных разрядов приведен в табл. 3.2.
Здесь делимым является информационный многочлен и^г\Х), делителем - порождающиймногочлен д(Х). Проверочные разряды определяются как коэффициенты многочлена Ь(Х), который представляет собой остаток отделения и^(Х) на д(Х).Для формирования кодового слова v по информационному вектору и используется цепь деления (рис. 3.8). Для получения проверочных разрядов, воспользуемся вычислениями, приведенными втабл. 3.2. Поместим информационные биты и = (1001) во входнойрегистр и обнулим разряды верхнего регистра формирователя остатка bo,bi,b2- Ключ выходного регистра находится в положении 51, ацепь обратной связи в устройстве деления замкнута. На первом тактестарший разряд двоичного информационного вектора «з заноситсяво выходной регистр сдвига, одновременно сумма щ и Ь% подается вцепь обратной связи регистра формирования остатка.Результат вычисления из © &2 = 1 заносится в разряды &о и ^1верхнего регистра. Обратим внимание на тот факт, что при вычислении первой промежуточной суммы в алгоритме деления Евклида(см.
табл. 3.2) происходит сложение <?i с щ и до с и%. Это в точностисоответствует сложению Ь\ = &о = 1 с разрядами, поступающимииз входного регистра сдвига (см. рис. 3.8) двумя и тремя тактами'позже. Таким образом, на нервом такте by = Ьц = 1, a. b2 = 0Замечание. Операция сложения производится по правилам арифметики по модулю 2 и обозначается знаком ©. Заметим, что варифметике по модулю 2, «-1» равна «+1» и операция вычитанияэквивалентна операции сложения,.182Глава 3. Циклические кодыSI СХ С$2ь«ь>U0*2Такт: л = 0 StartLJJLJ!••(,И| И 2V,V;V,l> 4V5VbКодовое словоИнформационноесловоТакт:л=1ЬоЬ,Ьг [ _ , *Sl<-\ °S2*o*i«-2L X JS1<A ° S 2boь,hSIS1<A ° S 2*ГТакт: л = 3[_;!>21-l-l-llU*«Такт:п =V,V5VjV4 V,Такт: n = 4ь2 L TР и с .
З.8. Кодер систематического циклического (7,4)-кодас порождающим многочленом д(Х) = 1 + X + X 3 .Так как схема получения кодового слова v по информационномувектору и остается неизменной во времени, то она обладает свойством линейности относительно операций в поле GF{2). Следовательно, многократные сдвиги и суммирования коэффициентов по-3.5. Схемная реализация циклического кодированиярождающего многочлена д(Х) и полученные промежуточные результаты соответствуют промежуточным результатам алгоритма деления Евклида (табл. 3.2).На втором такте разряд «2 загружается в выходной регистр формирования кодового слова. Одновременно вычисляется сумма мг сочередным значение Ьг- Результат u-i фЬг = 0 подастся в цепь обратных связей.
Таким образом, значение &о равно «О», а Ъ\ — Ьг = 1.На третьем такте в выходной регистр загружается информационный разряд щ и, одновременно, вычисляется сумма щфЬ2- Результатвычисления гц © Ъч = 1 поступает в цепь обратных связей и после==третьего такта Ьо &1 Ьг — 1На четвертом такте в выходной регистр заносится младший разряд щ. Вычисленное значение щ ф Ьг = 0 подается в цепь обратных=связей. В результате имеем Ьо = 0 и Ь\ = Ьг 15,0b0b\Р4SibiОбратная связьlololilv, v2v, v 4vsКодовое словоР и с . 3.9. Процедура считывания проверочных символов.Согласно алгоритму деления Евклида, после четвертого тактамногочлен Ь(Х) = &о + Ь\Х + Ь^Х2 равен остатку от деления и^г\Х)на д(Х).
Формирование проверочных символов завершено. На пятом, шестом и седьмом тактах проверочные символы &2> Ь\ и Ьо Дописываются к старшим* разрядам и(г\Х) кодового слова v(X). Дляэтого оба ключа предварительно' переводятся в положение 52 (рис.3.9).В рассмотренном примере показана реализация алгоритма деления Евклида с помощью регистра сдвига со встроенными сумматорами, поэтому данная схема не ограничивается приведеннымичисловыми значениями. Исходя из заданного многочлена д(Х) =1 + giX + д2Х2 Нhgr-\Xr~l + Xr, можно построить схему кодирования для любого двоичного циклического (п, &)-кода (рис.
3.10).Замечание. Таким, оке образом строятся кодеры дуальных циклических кодов с порождающим многочленом h(X).184Глава 3. Циклические кодыВыходной буфер с кодовыми символамипроверочныесимволы| информационныесимволыВходной буфер с информацией нымисимволамиРис.
3.10. Кодер систематического циклического (п,кода с порождающим многочленом д(Х).3.6. Синдром циклических кодов и контрольошибокРассмотрим модель передачи информации (рис.З.Н). При передачепо каналу связи с шумом к кодовому слову v(X) добавляется многочлен ошибок е(Х). В результате, многочлен принятого кодовогослова имеет вид:r(X)=v(X) + e(X)(3.64)r(X) = a(X)g(X) + s{X),(3.65)илигде s(X) представляет собой синдром.
Если г(Х) является кодовымсловом, то s(X) - нулевой многочлен.Кодовый многочлен\КодерПринятый многочленКанал/v(X)Информационный!многочленМногочлен ошибок— • « ( * )Инфорационныймногочлен последекодированияР и с . 3.11. Модель передачи информации.Синдром s(X) может быть вычислен с помощью алгоритма деления Евклида. Такое вычисление можно реализовать на простой цепи(рис. 3.12), во многом схожей с кодером систематического цикличе• ского кода (рис. 3.10). В схеме, приведенной на рис. 3.12, определяется остаток от деления некоторого многочлена на порождающий3.6. Синдром циклических кодов и контроль ошибок185,многочлен д(Х).
Сначала, в декодере производится обнуление двоичных разрядов синдрома so,s\,...,sr_i, и в регистр синдрома заносятся г первых принятых из канала бит. Остаток от деления г(Х)на порождаюгций многочлен д(Х) по алгоритму Евклида заноситсяв регистр синдрома. Рассмотрим процедуру вычисления синдромаs(X) на примере.Принятое словоРегистр синдромаРис.
3.12. Вычисление синдрома систематического (n,fe)кода с порождающим многочленом д(Х).Пример: Вычисление синдрома циклического (7,4)-кода Хэмминга.В качестве примера, рассмотрим уже известный циклический (7,4)код Хэмминга с порождающим многочленом д(Х) = 1 + X + X3.Пусть информационный вектор и = (1001). Как мы уже знаем изпредыдущего примера, этому вектору соответствует кодовое словоv = (011 1001).Регистр синдромаР и с .
3.13. Вычисление синдрома систематического (7,4)кода по принятому слову в канале без шума.Глава 3. Циклические кодыПри передаче но каналу без шума г = v. Процедура вычисления синдрома по тактам, в этом случае, представлена на рис. 3.13.Так как принятое из канала слово является кодовым, мы получимнулевой синдром.Пусть, из-за воздействия шума в канале произошла одна ошибкаг = (011 1011). Тогда, в результате вычисления остатка от деленияг(Х) на д(Х) (рис. 3.14), мы уже полу'чаем ненулевой синдром.
Таким образом, произошло распознавание ошибки.Такт л = 3Регистр синдромаР и с . 3.14. Вычисление синдрома систематического (7,4)кода при одиночной ошибке в принятом слове.Преимущества циклических кодов не ограничиваются одной лишьпростотой вычисления синдрома. Рассмотрим некоторые дополнительные свойства, которыми обладают их синдромы.Теорема 3.6.1. Пусть s(X) - синдром принятого из канала словаг(Х) некоторого циклического (п,/г)-кода. Обозначим через s\(X)остаток от деления многочлена X • s(X) на порождающий многочлен д{Х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
