Помехоустойчивое кодирование и декодирование (1151930), страница 4
Текст из файла (страница 4)
Он достигается при скоростях 1/3 ≤ k/n ≤ 3/4. При очень высоких и оченьнизких скоростях выигрыш от кодирования существенно уменьшается.Иногда целесообразно использовать коды с несколько худшей корректирующей способностью посравнению с лучшими известными кодами, но простые в реализации. К ним относятся коды, допускающиемажоритарное декодирование. Оно основано на возможности для некоторых циклических кодов выразитькаждый информационный символ с помощью Q различных линейных соотношений.
Решение о значениисимвола принимается по мажоритарному принципу. Для исправления всех ошибок до кратности lвключительно необходимо иметь 2l + 1 независимых соотношений.В некоторой области значений параметров мажоритарные коды имеют корректирующую способность,незначительно уступающую корректирующей способности кодов БЧХ.
В то же время их реализациясравнительно проста.Проиллюстрируем принцип мажоритарного декодирования на примере кода (7, 3) с проверочной матрицейb1 b21 0H 1 11 1 0 1b311b410b501b60001000010b7 00 .01 (9.17)Рассматриваемый код является циклическим с порождающим многочленом p(x) = x4 x3 x2 1. Онимеет кодовое расстояние d = 4.Используя матрицу (9.17), можно записать следующие соотношения для символа b1:b 1 = b 3 b 4 = b 2 b 6 = b 5 b 7.(9.18)С учетом (9.18) в декодере имеется возможность четырьмя разными способами вычислить первыйинформационный символ:b1I b%1; b1II b%3 b%4 ; b1III b%2 b%6 ; b1IV b%5 b%7 ,(9.19)где b%1b%2 ...b%7 — принятая кодовая комбинация.При отсутствии ошибок b1I b1II b1III b1IV , т.
е. все проверочные соотношения (9.19) дают один и тотже результат. При наличии одного ошибочного символа три проверочных соотношения дают правильноезначение, а соотношение, в котором участвует ошибочный символ, дает неверный результат. Принимаярешение по мажоритарному принципу, декодер выдает правильный символ b1.Пусть ошибочно приняты два символа. Если они входят в различные проверочные соотношения, то двапроверочных соотношения дадут значение 1, а два других — значение 0. В этом случае декодер выдает сигналотказа от декодирования. Если оба искаженных символа входят в одно проверочное соотношение, то всечетыре проверки дают один и тот же результат. Декодер выдает правильный символ b1.Аналогично определяются остальные информационные символы. Проверочные соотношения длясимволов b2 и b3 получаются из (9.19) циклической перестановкой:b I b% ; b II b% b% ; b III b% b% ; b IV b% b% ;2b3I2245237261 b%3 ; b3II b%5 b%6 ; b3III b%4 b%1; b3IV b%7 b%2 .Схема декодера (рис.
9.28) состоит из сдвигающего регистра, сумматоров по модулю 2 и мажоритарногоэлемента М. Простота ее обусловлена тем, что в данном случае каждый символ кодовой комбинацииучаствует в одном проверочном соотношении. Код, для которого выполняется это условие, называется кодомс разделенными проверками.Мажоритарное декодирование возможно и тогда, когда один и тот же символ участвует в несколькихпроверочных соотношениях.
Однако алгоритм декодирования усложняется.Простыми в реализации являются также итеративные и каскадные коды.Идея построения итеративных кодов заключается в следующем. Информационные символызаписываются в виде таблицы из k1 столбцов и k2 строк. К каждой строке таблицы дописываются n1 – k1проверочных символов в соответствии с некоторым кодом (n1, k1). Затем к каждому из n1 столбцов полученнойтаблицы добавляют n2 – k2проверочных символов вm2T1T2T3T4T5T6T7соответствии с некоторымкодом(n2,k2).ТакимВ хо добразом,строитсякодm2длиной n = n1n2 с числоминформационных символов km2= k 1k 2.ММожно показать, чтодляполученногодвумерногоm2В ы хо дитеративного кода кодовоерасстояние d равно d1d2, гдеd1 и d2 — кодовыеРис.
9.28. Структурная схема декодера циклического мажоритарногокода (7, 3)расстояния для кодов (n1, k1)и (n2, k2) соответственно.Кодовая комбинациядвумерного итеративного кода обычно передается последовательно по строкам, начиная с первой.Соответственно, декодирование ведется сначала по строкам, а затем, после приема всего двумерного блока, —по столбцам.Проиллюстрируем построение кодовой комбинации двумерного итеративного кода. Пустьинформационные символы записаны в виде таблицы1101101111000001.В качестве кодов (n1, k1) и (n2, k2) будем использовать коды с проверкой на четность. Тогда кодоваякомбинация будет иметь вид1101110111110000001110111Легко показать, что кодовое расстояние этого кода равно 4.
Код исправляет все однократные ошибки.Их координаты определяются по номерам строк и столбцов, в которых не выполняется проверка на четность.Одновременно код обнаруживает все двукратные ошибки.Итеративные коды характеризуются большой длиной, большим кодовым расстоянием и сравнительнопростой процедурой декодирования. Недостатком их является малая скорость k/n при заданной исправляющейспособности.Каскадные коды получаются комбинированием двух или более кодов и в некоторой степени похожи наитеративные.
Кодирование осуществляется следующим образом [133]. Множество k1k2 информационных символов(в дальнейшем предполагают, что они двоичные) разбивается на k2 подблоков по k1 символов. Каждый подблокиз k1 символов рассматривается как символ из алфавита объемом 2k1 . Затем k2 подблоков кодируютсякодовыми комбинациями внешнего кода (рис.
9.29), составленными из n2 подблоков по k1 двоичных символов.Наконец, каждый из n2 подблоков кодируется кодовыми комбинациями внутреннего (n1, k1)-кода. Полученноемножество n2 кодовых слов внутреннего (n1, k1)-кода является кодовым словом каскадного (n1n2, k1k2)-кода.Обычно в качестве внешнего используют код Рида—Соломона с основанием 2k1 , обеспечивающиймаксимальное кодовое расстояние при заданных n2 и k1, n2 < 2k1 , а в качестве внутреннего — двоичный (n1,k1)-код.Декодирование осуществляется следующим образом. Сначала декодируется внутренний код.
При этомполучается n2 подблоков, содержащих по k1 символов, которые декодируются внешним кодом. В результатена выходе внешнего декодера появляются k2 подблоков по k1 символов.ДекодированиедвумяВн еш н и йВ н утр е н н и йВ н утр е н н и йВн еш н и йотдельнымидекодерамиК аналк о д ерк од ердек о д ерде к о де рпозволяет существенно снизитьсложность по сравнению с той,В хо дВ ы хо дкотораяпотребуетсядляРис. 9.29. Схема каскадного кодированияполучения той же вероятностиошибки при одном уровнекодирования.Каскадные коды, как и итеративные, имеют большую длину и большое кодовое расстояние. Во многихслучаях они являются наилучшими среди блочных кодов.
В частности, для двоичного симметричного каналапри любой скорости передачи, не превосходящей пропускной способности канала, существует каскадный код,при котором вероятность ошибки может быть сколь угодно мала.Непрерывные (сверточные) кодыСверточный код — это линейный рекуррентный код. В общем случае он образуется следующимобразом. В каждый i-й тактовый момент времени на вход кодирующего устройства поступает k0 символовсообщения ai1ai 2 K aik0 .
Выходные символы bi1bi 2 K bin0 формируются с помощью рекуррентногосоотношения из K символов сообщения, поступивших в данный и предшествующие тактовые моментывремени:bim K / K 0 1k0 0j 1 c jm ai j ,m 1, 2, K, n0 ,где cjνm — коэффициенты, принимающие значения 0 или 1. Символы сообщения, из которых формируютсявыходные символы, хранятся в памяти кодирующего устройства. Величина K называется длиной кодовогоограничения.
Сверточный код имеет избыточность χ = 1 – k0/n0 и обозначается k0/n0.Типичные параметры сверточного кода: k0, n0 = 1, 2, …, 8; k0/n0 = 1/4, …, 7/8; K = 3, …, 10 [133].Кодирующее устройство сверточного кода может быть реализовано с помощью сдвигающего регистра исумматоров по модулю 2. Для схемы, показанной на рис. 9.30, на каждый символ сообщения вырабатываютсядва символа, которые последовательно во времени через коммутатор подаются в канал. Выходные символыявляются линейными функциями поступающего информационного символа и комбинации, записанной впервых двух разрядах регистра (логического состояния регистра). Связь между ячейками сдвигающего регистра исумматорами по модулю 2 удобно описывать порождающими многочленами qj (x), j = 1, 2, …, n0. Длярассматриваемого случая q1(x) = x2 1 (описывает связи верхнего сумматора) и q2(x) = x2 x 1 (описываетсвязи нижнего сумматора).
Наличие члена xi, i = 0, 1, 2, …, в порождающем многочлене означает, что (i + 1)-йразряд регистра сдвига соединен с сумматором. Счет разрядов регистра ведется слева направо.Сверточный код получается разделимым, если вm2каждый тактовый момент k0 выходных символов совпадают ссимволами сообщения.
На практике обычно используютсяb i1несистематические сверточные коды.TTT123В хо дРазличают прозрачные и непрозрачные сверточныеaib i2 В ы хо дкоды. Первые характеризуются свойством инвариантности поотношению к операции инвертирования кода, котороеm2m2заключается в следующем: если значения символов на входекодера поменять на противоположные, то выходнаясимволовтакжеинвертируется.Рис.
9.30. Структурная схема кодера сверточ- последовательностьСоответственно,декодированнаяпоследовательностьного кода (k0/n0 = 1/2, K = 3)символов будет иметь такую же неопределенность в знаке,что и принятая последовательность символов, а,следовательно, неопределенность знака последовательности можно устранить после декодированиясверточного кода (рис. 9.31). Указанное свойство прозрачных кодов особенно важно для СПИ, использующихпротивоположныеК о де рД е к о де рфазоманипулированныеT1T2с ве р то чн о гос вер то чн о гоК аналсигналы,которымкодакодасвойственноявлениеобратной работы.В хо дm 2 В ы хо дm2T3Для непрозрачного коданеопределенностьзнакапоследовательностисимволовР а зн о с тн ы йР а зн о с тн ы й к о дерде к о де рприходится устранять досверточного декодирования,Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
