А.И. Куприянов - Основы защиты информации (1022813), страница 26
Текст из файла (страница 26)
совокупность Ф коэффициентов — это число, 'авное передаваемому сообщению, увеличенное на (Ф-Ц по'ядков. Остаток от деления г(х) имеет степень не выше (Ф вЂ” й). :, аким образом, коэффициенты при ~с старших членах полинома ;: (х)х" ~®г(х) — это информационные символы; совпадающие " символами кодируемого сообщения, а при (Ф- ~) младших— оверочные символы. Эти свойства полиномов подсказывают схе' отехнические приемы построения кодеров циклического кода. я примера на рис.
5.3 приведена схема кодера для кода с порож-: ающим многочленом Р(х) = хз Ю х'Ю 1. Триггеры Т,, Т2 и Тз образуют регистр сдвига. В исходном состоии ключи К, и К2 находятся в положении 1. Кодируемая послеовательность С(х) подается на вход кодера и вместе с этим посту- 121 Вх 1 Выд К~ Рис.
5.3. Кодер циклического кода с порождающим полиномом Р(х) = хзвх2Е1 пает на выход ячейки Т2 (это соответствует умножению многочлена С(х) на х'). За четыре такта сдвига происходит деление много- члена С(х)хз на многочлен Р(х) =х'Юх2Ю 1. В результате в регистре записывается остаток, представляющий собой проверочные символы. Ключи К, и К2 перебрасываются в положение 2, и в течение трех следующих тактов содержащиеся в регистре символы поступают на выход кодера. От порождающего полинома Р(х) зависит корректирующая способность кода, поэтому его выбор очень важен. Необходимо помнить, что степень порождающего многочлена должна быть равна числу проверочных символов. Обнаружение ошибок при использовании циклических кодов сводится к делению многочлена В*(х) = В(х) + е(х), соответствующего принятой комбинации, на Р(х).
Если остаток г(х) оказывается равным нулю, то считается, что ошибки нет, в противном случае фиксируется ошибка. Полином г(х) = 1В(х) + е(х) 1то6Р(х) = е(х) п2одР(х) (5.22) зависит только от многочлена ошибок е(х) и играет ту же роль, что и вектор-синдром, Поэтому ошибки можно исправлять на основе таблицы соответствий между е(х) и г(х), сохраняемой в памяти декодера, как при линейных нециклических кодах. Однако свойство цикличности позволяет существенно упростить процедуру декодирования. Один из распространенных алгоритмов исправления ошибок использует следующие свойства синдрома циклического кода. Если имеется циклический код с кодовым расстоянием а~, исправля- Г ~-11 ющий все ошибки вплоть до кратности ~ — ~ включительно 2 (квадратные скобки, как и прежде, обозначают целую часть отно- д — 1 щения ), возможны следующие ситуации.
Если искажены 2 только проверочные символы, то вес синдрома будет меньше или 122 ~п — 11 ' н ~ ~, а сам синдром будет совпадать с вектором ошибок; вектор ошибки искажает хотя бы один информационный ~~-11 ' ол, то вес синдрома будетбольше ~ 2 ~; если г(х) — оста' от деления многочлена Ь(х) на Р(х), то остатком от деления '" нома Ь(х)х2 на Р(х) является многочлен г(х)х'шод Р(х), иначе ря синдром некоторого циклического сдвига многочлена Ь(х) '. ется соответствующим циклическим сдвигом синдрома ис' ого многочлена, взятого по модулю Р(х). ,: Работа алгоритма декодирования иллюстрируется схемой рис. 5.4 кода с порождающим полиномом Р(х) = х'Ю х2®1.
Такой код "еет кодовое расстояние д= 3. Он способен исправлять все одно- атные ошибки. ,::. Принятая кодовая комбинация одновременно поступает в бу- .рный регистр сдвига, служащий для ее запоминания и цикли'" кого сдвига, а также на устройство деления на многочлен Р(х) : вычисления синдрома. В исходном состоянии ключ находится : оложении 1.
После семи тактов принятая кодовая комбинация зывается полностью загруженной в буферный регистр, а в ретре устройства деления будет вычислен синдром. Если вес снима больше единицы, декодер начинает производить цикли' кие сдвиги комбинации в буферном регистре при отсутствии вой комбинации на входе и одновременно вычислять их синд''мы г(х)х' тос1 Р(х) в устройстве деления, Если на некотором 'и шаге вес синдрома окажется меньше двух, то ключ переходит -положение 2, обратные связи в регистре деления разрываются.
: ри последующих тактах ошибки исправляются путем подачи со" ржимого регистра деления на вход сумматора по модулю 2, вклю" нного в буферный регистр. После семи тактов работы декодера '-автономном режиме исправленная комбинация в буферном ре- од Рис. 5.4. Декодер циклического кода с порождающим полиномом Р(х) = хзвх2Е1 123 гистре возвращается в исходное положение (информационные символы будут записаны в старшие разряды). К циклическим кодам относятся коды Хемминга, которые являются примерами немногих известных совершенных кодов. Они имеют кодовое расстояние д= 3 и исправляют все одиночные ошибки.
Длина кода выбирается из условия 2~ ~ = Ф, которое имеет простой смысл: число различных ненулевых синдромов равно числу символов в кодовой последовательности. Так, существуют коды Хемминга (2'-1,2"- г-1), в частности коды (7,4), (15,11), (31,26), (63,57) и др. 122~. Ранее использованный в примерах многочлен Р(х) = х'Е х2Ю 1 является порождающим для кода Хемминга (7.4). Известно, что для любых целых положительных чисел т и (< Ф/2 существует двоичный код БЧХ длины Ф= 2 -1 с кодовым расстоянием а'> 2! + 1, причем число проверочных символов Ф- й< тЛ. Проще реализуется процедура мажоритарного декодирования, применимая для некоторого класса двоичных линейных, в том числе циклических кодов.
Основана эта процедура на том свойстве кодов, что у них каждый информационный символ можно несколькими способами выразить через другие символы кодовой комбинации. Если для некоторого символа эти способы проверки дают неодинаковые результаты (одни дают результат О, а другие 1, что может быть только в случае ошибочного приема), то окончательное решение по каждому из информационных символов принимается по мажоритарному принципу, т.е. по большинству.
Декодеры мажоритарных кодов выполняются на регистрах сдвига. Примером кода, допускающего мажоритарное декодирование, является уже выше циклический код (7,3). Мощные коды (т.е. коды с длинными блоками и большим кодовым расстоянием И) можно строить, объединяя несколько коротких кодов. Так строится, например, итеративный код из двух линейных систематических кодов (Ф,,~,) и (Ф2,7с,).
Вначале сообщение кодируется кодом первой ступени (Ф„~с,). Кодированная последовательность разбивается на блоки по й, символов. Эти символы считаются информационными для кода вгорой ступени, При кодировании на второй ступени к каждому блоку из Ц информационных символов приписываются (Л~, — й2) проверочных.
В результате получается блок, содержащий Ф,Ф, символов, из которых ~с,Ц являются информационными. Процесс формирования кода можно дополнить третьей итерацией, четвертой и т.д. При декодировании обнаруживают и исправляют ошибки каждого блока: сначала первой ступени, затем— второй. При этом исправляются только те ошибки, которые не были исправлены кодом первой ступени. Минимальное кодовое расстояние для двухмерного итеративного кода равно произведению минимальных кодовых расстояний для кодов первой и второй ступеней, т.е. Н= ~Щ. 124 '-'::На итеративный код похож каскадный код, но между ними тся существенное различие. Первая ступень кодирования в :кадном коде осуществляется так же, как в итеративном. После как сформированы К, блоков кода первой ступени (внутрен- ), каждая последовательность из /с, двоичных (информацион": ) символов внутреннего кода рассматривается как один сим, недвоичного кода второй ступени (внешнего).
Основание это'' кода ч = 2»'. К этим символам приписываются еще (Ф2 — й2) ' верочных символов т-го кода также в вице строк длиной Ф~. К ой из этих строк приписываются двоичные проверочные симы в соответствии с внутренним кодом Ф,,/с,. ;: В процессе приема сначала декодируются (с обнаружением или :правлением ошибок) все блоки внутреннего кода, а затем деруется блок внешнего т-го кода (Ф2,12), причем исправля: я ошибки, оставшиеся после декодирования внутреннего кода. ::качестве внешнего кода используют обычно и-й код Рида — Со'мона, обеспечивающий наибольшее возможное значение а~ при нных И~ и Ц, если И,<т. :::: Сверточный код — это линейный рекуррентный код.
В общем ае он образуется следующим образом. В каждый (-й тактовый ' мент времени на вход кодирующего устройства поступает Ц волов сообщения: слса... с; о. Выходные символы ЬлЬа ... Ь;~офоруются по рекуррентному правилу из символов сообщения, поивших в данный и предшествующие тактовые моменты вреени. Величина lс называется длиной кодового ограничения. Она казывает, на какое максимальное число выходных символов вли'т данный информационный символ. Эта величина играет для рточного кода ту же роль, что и длина блочного кода.
Сверточй код имеет избыточность т = 1 — Ц/Фо. Обозначение такого Ма (к /Фо). Кодер сверточного кода может быть реализован с помощью ': вигающего регистра и сумматоров по модулю 2. Кодирующее стройство, выполненное по схеме (рис. 5.5), на каждый символ :ообщения вырабатывает два символа выходной последователь- 'ости, которые по очереди подаются на выход через коммутатор. Выходные символы формируются в результате линейного преразования входного информационного символа и комбинации, Рис. 5.5.
Кодер сверточного кода 125 записанной в первых двух разрядах регистра. Связь между ячейками сдвитающего регистра и сумматорами по модулю 2 удобно описывать порождающими полиномами Я(х), у'е 1: Ф. Для конкретного примера кодера (см. рис. 5.5) 9(х) = х291 описывает связи верхнего сумматора и Щх) = х2 Юх® 1 описывает связи нижнего сумматора. Наличие члена х', 1= 0,1,2, ... в порождающем много- члене означает, что (1+ 1)-й разряд регистра сдвига соединен с сумматором. Нумерация разрядов регистра — слева направо. Сверточный код получается систематическим, если в каждый тактовый момент Ц выходных символов совпадает с символами сообщения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
