Реферат: Избыточные коды

Заметим, что строки проверочной матрицы линейно независи­мые. Поэтому проверочную матрицу можно использовать в ка­честве порождающей для некоторого другого линейного кода (п, п-k ), называемого двойственным.

Кодирующее устройство для линейного (п,k ) кода (рис. на предыдущей стр.) состоит из k -разрядного сдвигающего регистра и r=п-k бло­ков сумматоров по модулю 2. Информационные символы одно­временно поступают на вход регистра и на выход кодирующего устройства через коммутатор К. С поступлением k -го информаци­онного символа на выходах блоков сумматоров в соответствии с уравнениями (7.11) формируются проверочные символы, которые затем последовательно поступают на выход кодера. Процесс декодирования сводится к выполнению операции

, ??? S ? ?????? ???????????? (п-k) , ?????????? ?????????, В - ?????? ???????? ??????? ??????????.
???? ???????? ?????????? В ????????? ? ????? ?? ??????????? ? (??? ????? ????? ?????, ????? ???? ?????? ? ???????? ???????? ???????????, ???? ??-?? ???????? ????? ???? ??????????? ??????? ?????????? ????????? ? ??????), ??
? ????????? ?????? S≠O, ?????? ??? ???????? ??????? ?????? ?? ??????? ?????? е . ?????????????,

где В- вектор, соответствующий передаваемой кодовой комби­нации. При S=0 декодер принимает решение об отсутствии оши­бок, а при S≠O - о наличии ошибок. По конкретному виду синдрома можно в пределах кор­ректирующей способности кода указать на ошибочные символы и их исправить.

Декодер линейного кода (рис. на следующей стр.) состоит из k - разрядного сдвигающего регистра, (п-k) блоков сумматоров по модулю 2, схе­мы сравнения, анализатора ошибок и корректора. Регистр слу­жит для запоминания информационных символов принятой кодо­вой последовательности, из которых в блоках сумматоров формируются проверочные символы. Анализатор ошибок по конкретно­му виду синдрома, получаемого в результате сравнения формиру­емых на приемной стороне и принятых проверочных символов, оп­ределяет места ошибочных символов. Исправление информацион­ных символов производится в корректоре. Заметим, что в общем случае при декодировании линейного кода с исправлением ошибок в памяти декодера должна храниться таблица соответствий между синдромами и векторами ошибок. С приходом каждой кодовой комбина­ции декодер должен перебрать всю таблицу. При небольших зна­чениях (п-k) эта операция не вызывает затруднений. Однако для высокоэффективных кодов длиной п , равной нескольким десяткам, разность (п-k) принимает такие значения, что перебор таблицы оказывается практически невозможным. Например, для кода (63, 51), имеющего кодовое расстояние d =5 , таблица состоит из 2^12 = 4096 строк.

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

Циклические коды.

Циклические коды относятся к классу линейных системати­ческих. Поэтому для их построения в принципе достаточно знать порождающую матрицу.

Можно указать другой способ построения циклических кодов, основанный на представлении кодовых комбинаций многочлена­ми b(х) вида:

??? bn-1bn-2...bo - ??????? ??????????. ??? ??????? ????????????? ????? ??????????? ??? ?????????????? ???????? ? ??????? ????, ??? ???????? ????? ?????????????? ?? ?????? 2.

Каждый циклический код ( n , k ) характеризуется так назы­ваемым порождающим многочленом. Им может быть любой мно­гочлен р (х) степени n - k . Циклические коды характеризуются тем, что многочлены b (x) кодовых комбинаций делятся без остатка на р (х) . Поэтому процесс кодирования сводится к отысканию многочлена b (x) по известным многочленам a(х) а р (х) , делящегося на р (х) , где a(х)- многочлен степени k-1 , соответствующий информацион­ной последовательности символов.

????????, ??? ? ???????? ?????????? b (x) ????? ????????????? ???????????? a(х) р(х) . ?????? ??? ???? ?????????????? ? ??????????? ??????? ??????????? ?????????????, ??? ??????????? ??????? ?????????????. ??????? ?? ???????? ? ???????? ??????????? ????????? ????? ?????????? ?????????? b (x) .
??????? ????????? ?(?) ?? ? ?????????? ???????????? ???????? ?? р (х) . ????? (7.12)

где m(х) - частное, а с (х) - остаток. Так как операции сумми­рования и вычитания по модулю 2 совпадают, то выражение (7.12) перепишем в виде: (7.13)

?? (7.13) ???????, ??? ????????? ??????? ?? р (х) ?, ?????????????, ???????? ???????.

Многочлен имеет следующую структуру: первые n - k членов низшего порядка равны нулю, а коэффициенты осталь­ных совпадают с соответствующими коэффициентами информа­ционного многочлена а (х) . Многочлен с (х) имеет степень мень­ше n - k . Таким образом, в найденном многочлене b (x) коэффициенты при х в степени n - k и выше совпадают с информацион­ными символами, а коэффициенты при остальных членах, опре­деляемых многочленом с (х) , совпадают с проверочными сим­волами. На основе приведенных схем умножения и деления многочле­нов и строятся кодирующие устройства для циклических кодов.

В качестве примера приведена схема кодера и декодера для кода (см. рис.) с порождающим многочленом:

??? ????? ??????? ?????????? d =3, ??? ????????? ??? ??????????? ??? ??????????? ??????.

Принятая кодовая комбинация одновременно поступает в бу­ферный регистр сдвига, служащий для запоминания кодовой ком­бинации и для ее циклического сдвига, и на устройство деления на многочлен р (х) для вычисления синдрома. В исходном состоянии ключ находится в положении 1. После семи тактов буферный ре­гистр оказывается загруженным, а в регистре устройства деления будет вычислен синдром. Если вес синдрома больше единицы, то декодер начинает производить циклические сдвиги комбинации в буферном регистре при отсутствии новой комбинации на входе и одновременно вычислять их синдромы s( x) xi modp( x) в устрой­стве деления. Если на некотором 1-м шаге вес синдрома окажет­ся меньше 2, то ключ переходит в положение 2, обратные связи в регистре деления разрываются. При последующих тактах ошиб­ки исправляются путем подачи содержимого регистра деления на вход сумматора по модулю 2, включенного в буферный регистр. После семи тактов работы декодера в автономном режиме ис­правленная комбинация в буферном регистре возвращается в ис­ходное положение (информационные символы будут занимать старшие разряды).

Существуют и другие, более универсальные, алгоритмы деко­дирования.

К циклическим кодам относятся коды Хэмминга, которые яв­ляются примерами немногих известных совершенных кодов. Они имеют кодовое расстояние d=3 и исправляют все одиночные ошибки. Среди циклических кодов широкое применение нашли коды Боуза- Чоудхури- Хоквингема (БЧХ).

Сверточные коды

Методы описания сверточных кодов.

Кодер СК содержит регистр памяти для хранения опреде­ленного числа информационных символов и преобразователь информационной последовательности в кодовую последовательность. Процесс кодирования производится непрерывно. Скорость кода R = k / n , где k - число информационных символов, одновременно поступающих на вход кодера, n - число соответствующих им символов на выходе кодера. Схема простого кодера показана на рис. 1.1а.

Информационные двоичные символы u поступают на вход регистра с К разрядами. На выходах сумматоров по модулю 2 образуются ко­довые символы a(1) и a(2). Входы сумматоров соединены с определенными разрядами регистра. За время одного ин­формационного символа на выходе обра­зуются два кодовых символа (R = 1/2 ). Возможно кодирование и с другими скоростями. При скорости 2/3 на вход кодера одновременно поступает k =2 информационных символа, на выходе при этом образуется n =3 кодовых символа. Схема такого кодера показана на рис. 1.1,6.

Рассматриваемый код называется сверточным, постольку последователь­ность кодовых символов а может быть определена как свертка информационных символов u с импульсным откликом кодера. На рис. 1.2 показано прохожде­ние единичной последовательности u =100… через кодер.

Символы a(1) и a(2) на его выходе образуют импульсный отк­лик h= 00111011 00... Таким образом, если на входе кодера действует произвольная информационная последователь­ность и, то последовательность на его выходе есть сумма по модулю 2 всех импульсных откликов, обусловленных действием смещенных во времени символов 1. Сверточный кодер, как автомат с конечным числом состоя­ний, может быть описан диаг­раммой состояний. Диаграмма представляет собой направлен­ный граф и описывает все воз­можные переходы кодера из од­ного состояния в другое, а так­же содержит символы выходов кодера, которые сопровожда­ют эти переходы.

Первоначально кодер находится в состоянии 00, и поступление на его вход информационного символа u =0 перевозят его также в состояние 00. При этом на выходе кодера будут символы a(1)a(2)=00. На диаграмме этот переход обозна­чается петлей 00, выходящей из состояния 00 и вновь возвращающейся в это состояние. Далее, при поступлении символа u =1 кодер переходит в состояние 10, при этом, на выходе будут символы a(1)a(2)=11. Этот переход из состояния 00 в состояние 10 обозначается пунктирной линией. Далее воз­можно поступление на вход кодера информационных симво­лов 0 либо 1. При этом кодер переходит в состояние 01 либо 11, а символы на выходе будут 10 либо 01 соответствен­но. Процесс построения диаграммы заканчивается когда бу­дут просмотрены все возможные переходы из одного состоя­ния во все остальные.

Решетчатая диаграмма является разверткой диаграммы состояний во времени. На решетке состояния показаны узлами, а пе­реходы соединяющими их линиями. После каждого пере­хода из одного состояния в другое происходит смещение на один шаг вправо. Решетчатая диаграмма дает наглядное представление всех разрешенных путей, по которым может продвигаться кодер при кодировании. Каждой информацион­ной последовательности на входе кодера соответствует един­ственный путь по решетке. Построение решетки производится на основе диаграммы состояний. Исходное состояние S(1)S(2)=0. С поступлением очередного символа u =0 либо 1 воз­можны переходы в состояния 00 либо 10, обозначаемые вет­вями 00 и 11. Процесс следует продолжить, причем через три шага очередной фрагмент, решетки будет повторяться. Пунктиром показан путь 11100001..., соответствующий по­ступлению на вход кодера информационной последовательности 1011...

??? ???????? ?????? ?????????????????? ???????? ?? ??? ????? ? ?????? ???????????? ? ?????????????? ????????? ????????:

Здесь индексы в скобках обозначают: i - номер входа коде­ра, 1≤ j ≤ n , j - номер выхода кодера, 1≤ i ≤ k . Индексы без скобок (0, 1, 2, ...) обозначают дискретные моменты времени.

??????? ??????????? ????? ???? ??????????? ??? ????????? ?????????? ??????? ?????????????? ??????????????????? u ( D ) ?? ??????????? ?????????? ???? G(j)(D), ???????? ????????? ????? ????? ???????? ?????? ? ??? ???????? (1.1):

Порождающий многочлен представим в виде ряда (1.2):

СК можно также задавать порождающей матрицей (1.3):

??????????? ??????? ??????? ?? ??????? ???????? ???????????? ??????? (??????? ?????? ??????? ?), ???????, ? ???? ???????, ??????? ?? ????????????? ?????? G i , 0≤ i ≤ k -1 , ?????????? k ????? ? n ?????????. ?????????? ???? ?????? ???????? ????? ???????? ???????? 0 ? 1.

Как при использовании блоковых кодов, процесс кодирования может быть представлен в матричной форме: A = UG (1.4)

,где U - полубесконечная матрица входных информационных символов, А - полубесконечная матрица символов на выходе кодера.