Главная страница  Алгебраическая теория кодирования 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [ 61 ] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78]

(15.331)

-10,

Пусть С(*) = [С(), С[), . . ., С1, С] - характеристическая функ.\ ция множества Ai, определенная равенствами!

1, если aAi]

если Ai.

Здесь и = 2"" - 1 и по определению а°° == 0.

Определим, далее, покомпонентное произведение ) СО и С) как слово, задаваемое умножением соответствующих компонент

(15.332) C«> = C<, Cl C<b

15.34. Теорема. Каждое кодовое слово двоичного РМ-кода\ порядка г может быть записано в виде многочлена степени не выше г\ от переменных C(i), Cf), . . ., СС").

Замечания. В качестве свободного члена хмногочлена выби- рается единичный вектор 1.

Казами, Лин и Питерсон доказали также теорему 15.34 для] недвоичных ОРМ-кодов. В недвоичном случае в качестве С<>,1 С(), . . ., С™) выбираются некоторые специальные кодовые слова РМ-кода первого порядка; эти слова не могут быть определены! соотношением (15.331), но их произведение определяется форму-! лой (15.332).

Доказательство, Слово

(15.341) .С(*>® С*® ... ®С-

- характеристическая функция (т - /)-мерного подпространства! i, П П • • . П пространства (2") над GF (2). Если!

< г, то по теореме 11.64 (или свойству 15.329) слово (15.341) являет-! ся кодовым словом РМ-кода порядка г. Число слов вида (15.341)j

равно 2 ( 7 ) ° согласно 15.324, оно совпадает с числом информа-j j=o I

ционных символов РМ-кода порядка г. Для доказательства того, что! все слова вида (15.341) линейно независимы, заметим, что характери-!

стическая функция любого элемента из GF (2"), скажем, 2

"* I

может быть представлена в виде многочлена Ц [С** -f- (1-Ь Ui) 1

i= 1 f

от С<*) степени < т. Таким образом, 2™ слов вида (15.341) линейно! ) Казами, Лин и Питерсон употребляют термин «векторное произведение»-!

независимы, и 2(7) этих слов, степени которых г, обра-

зуют базис векторного пространства РМ-кода порядка г. щ

15.35. Теорема. Каждый РМ-код с блоковой длиной N = 2 инвариантен относительно любой подстановки, переводящей все аффинные подпространства пространства GF (2") над GF (2) в аффинные подпространства. Группа всех таких подстановок трижды транзита i

тивна, и ее порядок равен 2™ [] (2"" -2).

Доказательство. Каждое кодовое слово РМ-кода порядка г есть сумма слов, представляющих собой характеристические функции аффинных подпространств размерностей т - г, и каждая сумма характеристических функций аффинных подпространств размерности - г является кодовым словом. Следовательно, каждая подстановка, переводящая аффинные подпространства из GF (2"") в аффинные подпространства, должна сохранять РМ-коды.

Любой из 2™ линейных сдвигов пространстЬа GF (2™) переводит аффинные подпространства в аффинные подпространства; следовательно, порядок группы всех подстановок равен порядку подгруппы, сохраняющей нуль пространства GF (2™), умноженному на 2™. •Эта подгруппа переводит любое линейное подпространство GF (2") в другое линейное подпространство. Любой упорядоченный базис пространства GF (2™) под действием подстановок этой подгруппы должен переходить в другой упорядоченный базис. Следовательно, порядок подгруппы, оставляющей на месте нуль из GF (2™), равен числу упорядоченных базисов двоичного т-мерного векторного про-

странства, которое по теореме 11.52 равно [] (2™ - 2). щ

i = 0

(оо) (0,1,2,3,4,5,6,7,8,9,10,11,12,13,14)

(Подразумевается, что а°° -v а°°, а"а* ... а а")

Л2: Aq-Ai!x-\-A2Ci.-\-AsOi? ->- Ао-\-Аза,-\-(Ai-\- AiaАа (оо)(0)(1,2,3,5,6,11,9) (4,8,14,10,13,12,7)

Пз : +Л1 а+Л4- Лза»- + Лi а за + (2 + А) «з (со) (0) (1) (4) (2,3,6) (5,9,11) (7,10,12) (8,14,13)

Я4 : Ло -Ь Лla + 2а2+Аа Ло -- Лjа+Л+(Лз +1) а (00,3) (0,14) (1,9) (2,6) (4,7) (5,11) (8,13) (10,12)

Рис. 15.3 Некоторые подстановки, сохраняющие РМ-коды длины 16.

Для иллюстрации теоремы 15.35 на рис. 15.3 приведен пример некоторых подстановок, сохраняющих РМ-код с блоковой длиной 16. Для записи подстановок используется описание поля GF (2*), приведенное в столбце 7 таблицы 4.1.



15.4. Пороговое декодирование - лучший из известных алгоритмов] декодирования некоторых кодов

Так как кодовые слова РМ-кодов образуют подмножество множе-1 ства кодовых слов БЧХ-кода, то к РМ-кодам применимы алге-i браические алгоритмы декодирования БЧХ-кодов. Однако; к РМ-кодам с малыми скоростями применим и более простой алго-j ритм, известный под названием порогового декодирования. Впервые ё один из вариантов порогового декодирования для кодов Рида - i Маллера был описан Ридом [1954]. Для некоторых других классов блоковых кодов процедуры порогового декодирования были впервые! введены Месси [1963].

Метод порогового декодирования мы объясним на последователь-, ности примеров.

15.41. Двоичные коды длины « = 2"* - 1с повто- рением. Начнем с простейшего случая 1-укороченного РМ-кода; нулевого порядка, представляющего собой двоичный код с повторе-; нием. При декодировании для этого кода достаточно подсчитывать

Нзкшюла

Q-O-4-П

Установить в нулевое попаяевше

Элемент ИЛИ

----* т-разрядный счётчик

Читать выход

о ♦

к получателю • данных

Рис. 15.4. Декодер для 1-укороченного РМ-кода нулевого порядка.

число единиц среди п = 2" - 1 полученных символов. Если получено более ге/2 единиц, то принимается решение, что передавалось единичное кодовое слово; если получено меньше п12 единиц, то принимается решение, что передавалось нулевое кодовое слово. Непосредственный метод реализации этого решающего правила представлен на рис. 15.4. Декодер содержит ж-разрядный счетчик и /тг-ячееч-: ный регистр сдвига с обратной связью (OGP). В начальном состоянии счетчик установлен на нуль, а ОСР содержит 00 ... 01. Символы, поступающие из канала связи, складываются в счетчике. Переход! ОСР снова в состояние 00 ... 01 означает, что все 2"* - 1 символов-

П1)иняты. Наивысший разряд счетчика равен 1 тогда и только тогда, ;огда среди принятых символов содержалось не менее 2"" единиц. Наивысший разряд счетчика выдается на выход, а сам он устанавливается в нулевое положение, чтобы приготовиться к приёму следующего блока из 2™ - 1 символов.

Двоичный код с повторением описывается следующими прове-])очными соотношениями:

0 = Co-fCi,

0=0 -гг,

!]5.42)

0 = Со

+ Сз,

Каждое из этих проверочных уравнений связывает Со и один из других символов. Более того, никакая пара проверочных соотношений ие содержит общих символов, за исключением Cq. Поэтому каждое из уравнений определяет независимое значение Со:

если 1 = 0;

i?2, если £"2 = 0;

i?3, если £"3 = 0;

Со =

Если не более половины координат вектора шума Е, Е, . . ., £„-1 равны 1, то решение о Cq можно принять «по большинству голосов» для {Щ.

Уравнения (15.42) представляют собой простейший пример системы ортогональных проверок. В общем случае имеет место следующее определение:

15.43. Определение. Множество проверочных уравнений называется ортогональным на множестве позиций Р = {i, j, . . ., к} тогда и только тогда, когда

1) Ei входит во все проверочные уравнения множества для любого ieP;

2) Ei входит не более чем в одно проверочное уравнение множества для любого i $ Р.

15.44. ОСР-к оды максимальной длины. Рассмотрим далее 2-укороченные РМ-коды первого порядка, совпадающие с ОСР-кодами максимальной длины. Так как совершенные коды Хэмминга, исправляющие одну ошибку, дуальны к этим кодам,

го такой код удовлетворяет проверочному уравнению 2 Cj = 0 тогда ц только тогда, когда = 0. В частности, для любой задан-

ПОЙ пары позиций {i, j) код содержит проверочные соотношения



Р {i, j, к} веса 3, связывающие эти символы, где а** = + а\ Следовательно, для любой заданной позиции можно выбрать (п - 1)/2 проверочных соотношений веса 3, ортогональных на этой позиции. Например, предположим, что /п = 4иа* = а + 1. Тогда, ортогональными на нулевой позиции будут следующие семь проверочных множеств: {О, 1, 4}, {О, 2, 8}, {О, 3, 14}, {О, 5, 10}, {О, 6, 13}, (О, 7, 9}, (О, И, 12}. Если в канале произошло не более трех ошибок, то Со может быть определено «по большинству голосов» из следующих восьми равенств:

(15.45)

С„ =

-ffe + -13, 11+ -12,

если если если если если если если если

У?,+ £4 = 0

2+J?8=0 i?3-b£l4=0 £5+10=0

e + Ji3 = 0

£7+9=0

11 + 12 = 0; Jo = 0.

Если не менее пяти из этих величин совпадут, то «голосование»! обеспечит наиболее вероятное значение Со. Если четыре из этих равенств дадут Со = 1, а остальные четыре - Со = О, то пороговая процедура приведет к нарушению декодирования, что позволит; обнаружить четыре или более ошибок в канале.

Для того чтобы избежать этой «пробки», рассмотрим вероятности различных оценок (15.45). В двоичном симметричном канале с вероятностью ошибки Р имеем

Рг {Eo = 0) = i- Р, Рг [Et + Ej = 0) = (1 - Pf + PK

Если О < P < 1/2, то {\- Pf + Р<\- Р, так что значение, Со = Ro имеет большую вероятность, чем все остальные. На этой основе можно построить более тонкий пороговый декодер, который при делении голосов «четыре на четыре» дает оценке Сд = Rq дополнительный голос.

Декодер на рис. 15.5 вычисляет согласно 15.45 все восемь оценок. Сначала к нулевому состоянию счетчика добавляется 2i?o. Затем вычисляется величина Ri + Нж складывается с содержимым счет-; чика. После этого кодовое слово подвергается подстановке я", показанной на рис. 15.3. Эта подстановка не трогает позиции О, но; переставляет 2-ю и 8-ю позиции соответственно с 1-й и 4-й. Затем? вычисляется новая проверочная сумма и добавляется к содержимому \ счетчика. После вычисления всех восьми величин по большинству! голосов» определяется Cq. Далее осуществляется циклический!

сдвиг кодового слова и процесс повторяется для определения Cj, ба, . . ., С„ 1.

Хотя схема декодирования рис. 15.5 использует только один сумматор полученных символов, для декодирования с ее помощью одного символа слова требуется осуществить 7 перестановок. На

[0] й Ц М н Й Й ш И Й И i р р р


Рис. 15.5. Перестановочно-пороговый декодер для ОСР-кода, л = 15.

]1ис. 15.6 приведена схема с большим быстродействием, позволяющая вычислять все восемь оценок одновременно. Счетчик на рис. 15.5 заменен на рис. 15.6 пороговым элементом - элементом без памяти.

Ijji

Порог 4j

Рис. 15.6. Пороговый декодер для ОСР-кода, п=:15.

.мгновенный выход которого равен единице тогда и только тогда, когда не менее Т из его входов равны единице. Хотя конструкция порогового элемента, основанная на элементах И, ИЛИ и НЕ (см. ]шс. 2.1), очень сложна и требует многих компонентов, существует много технологических способов построения порогового элемента в виде единственного компонента. Например, пороговый элемент может быть выполнен в виде единого металлического тора. Каждый




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [ 61 ] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78]

0.0234