Декодер циклического кода

Декодер циклического кода

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и технике связи. Его использование в системах передачи дискретной информации с применением двоичной относительной фазовой модуляции (ОФМ) позволяет повысить достоверность декодирования кода, принятого из канала с ОФМ. Декодер содержит буферный накопитель 1, блок 2 формирования синдрома, блок 4 вычисления локаторов ошибок, блок 6 вычисления поправок и сумматор 8 по модулю два. Благодаря введению блока 3 формирования синдрома, блока 5 вычисления локаторов ошибок, блока 7 вычисления поправок, сумматоров 9-11 по модулю два, элемента 12 задержки, буферных накопителей 13, 14, элементов ИЛИ 15-18, триггеров 19-21 и элементов И 22, 23 в декодере исправляются ошибки от сбоя фазы при сохранении исправляющей способности кода к комбинации независимых ошибок. 1 ил.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (l9) (ll) А1 (51)5 Н 03 М 13/02 описяник иэоБрят НиЯ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

MPH rHHT СССР

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

1 (2 1) 4626244/24-24 (22) 26.12.88 (46) 15.10.90. Бюл. È 38 (72) А.Э. Нейфах (53) 621.394.147Ф681..32(088.8) (56) Авторское свидетельство СССР

Р 1293855, кл. Н 03 M 13/02, 1985.

Авторское свидетельство СССР

N - 233736, кл. Н 03 М 13/02, 1965, Берлекэмп Э. Алгебраическая теория кодирования.. M.: Мир, 1971, с. 238240.

Блох Э.Л., Зяблов В.В. Обобщенные каскадные коды. M.: Связь, 1976, с. 109-120, рис. 3.4 1. (54) ДЕКОДЕР ЦИКЛИЧЕСКОГО КОДА (57) Изобретение относится к вычислительной технике и технике связи.

El o использование в системах передачи дискретной информации с примене2 нием двоичной относительной фазовой модуляции (ОФМ) позволяет повысить достоверность декодирования кода, принятого из канала с ОФМ. Декодер содержит буферный накопитель 1, блок 2 формирования синдрома, блок 4 вычис.— . ления локаторов ошибок, блок 6 вычисления поправок и сумматор 8 по модулю два. Благодаря введению блока 3 формирования синдрома, блока 5 вычисления локаторов ошибок, блока 7 вычисления поправок, сумматоров 9-11 по модулю два, элемента 12 задержки, буферных накопителей 13, 14, элементов

ИЛИ 15-18> триггеров 19-21 и элементов

И 22, 23 в декодере исправляются ошибки от сбоя фазы при сохранении исправляющей способности кода к комбинации независимых ошибок. 1 ил. 1599996

Изобретение относится к вычислительной технике и технике связи и может быть использовано в системах пе редачи дискретной информации с приме5 нением двоичной относительной фазовой модуляции (ОФМ).

Цель изобретения — повышение достоверности декодирования кода, принятого из канала с ОФМ.

1О

На чертеже приведена функциональная схема декодера.

Декодер циклического кода содержит . первый буферный накопитель 1, первый и второй блоки 2, 3 формирования синдро-.! ма,первый и второй блоки 4, 5 вычисления локаторов ошибок, первый и второй блоки 6,7 вычисления поправок, первый— четвертый сумматоры 8-1 1. по модулю два, элемент 12 задержки, второ»» и третий буФерны)» накопители 13,14,первый — четвертый элементы ИЛИ 15-18, первый — третий триггеры 19-21, первый и второй элементы И 22, 23. На чертеже обозначены информационный вход 24, вход 25 обнуления, информационный выход 26 и выход 27 ошибки.

Буферные накопители 1, 13, 14 представляют собой регистры сдвига.

Элемент 12 обеспечивает задержку 3О сигнала на один такт, т.е. является

1 разрядом такого же регистра сдвига.

Блоки 2, 3 формирования синдрома выполнены на основе схем формирования остатка отделения в поле Галуа и метричного умножения в соответствии с выбранными кодами.

Блоки 4, 5 вычисления локаторов ошибок могут быть выполнены, как в прототипе (4).

Блоки 6, 7 вычисления поправок

40 реализуются так же, как в 4, причем на их вторых выходах формируются сигналы, свидетельствующие о наличии неисправимой ошибки, Работа всех указанных блоков тактируется с распределителя импульсов (не показан).

В основе работы декодера лежит следующее.

Относительная фазовая модуляция получила широкое распространение для передачи дискретной информации по каналу связи. Однако применение корректирующих кодов в системах передачи дискретной информации затруднено эффектом преобразования одиночных ошибок в двойные смежные, поскольку при

ОФМ искажение j-го бита в канале связи вызовет также искажение (j+1)-ro бита. Поэтому исправляющая способность обычного декодера, подключенного на выходе демодулятора, понижается примерно в два раза.

Используя введенное в $2) понятие фиктивного кода, который для одинаковых ошибок в канале связи образует те же синдромы при передаче по схеме с

11 - tt абсолютной модуляцией, какие порождает реальный код при передаче в ОФМ, можно полностью использовать исправляющую способность реального кода, который имеет длину и число информационных символов на 1 меньше, чем со— ответствующие числа для фиктивного

1 кода, Иначе говоря, возможность исправления ошибок, вызванных сбоями фазы и, одновременно, сохранение исправляющей способности кода для обычных ошибок при передаче сигнала ОФМ можно реализовать, если один и тот же код испольэовать для исправления ошибок в двух режимах: в режиме фиктивного кода и в обычном режиме. Эта возможность имеет место для таких кодов,которым соответствуют фиктивные коды, являю)циеся циклическими кодами.

Для рассматриваемых двоичных кодов

2) показано, что циклическому (nq, К 1 — коду длиной и = 2 — 1 (здесь

9 11

m — целое число) с минимальным весом

d, порождающий многочлен которого р (х) не содержит множителя х+1, соответствует реальный (и, К)-код, и = и — 1, К К, — 1 с минимальным весом d = d . При этом реальным кодом является специальным образом укороченЮ ный циклический код с порождающим многочленом g (х) =8»(х) ° (х+ 1) у (и+1, К) кода полной дл)»ны с порождающим много" членом g(x), который ниже будем называть дополнительным кодом, удален крайний проверочный символ, а не информационные символы, как у обычных укороченных циклических кодов.

Декодер функционирует следующим образом.

Перед приемом каждого нового кодового слова сигналом со входа 25 триггеры 19-21 обнуляются. Синдром, вычисляемый различным образом в формирователях синдрома 2,3 (соответственно для реального и фиктивного кодов) при поступлении из канала связи на вход 24 кодового слова, используется в блохах

4,6, как синдром реального кода, а в блоках 5,7, как синдром фиктивного

5 > 1599996 6 кода. Поправка, вычисляемая блоком 6, исправленной информации, выделяе прибавляется в сумматоре 8 к информа- сумматором 11. Это позволяет снизу. ции, задержанной буферным накопителем вероятность необнаруженной ошибки в

1 непосредственно а поправка опре- информации в случае появления неиспр р р

5 деленная блоком 7, прибавляется K HH- равляемой комбинации ошибок. формации в сумматоре 10 дважды, по- Рассмотрим особенности функционискольку при ОФМ искажение j-ro симво- рования блоков 2-7 декодеров реальла в канале связи вызовет инвертиро- ного и фиктивного кодов при использование j-ro и (j+1)-го символов для ванин итеративной процедуры декоди!

О

1-(п-1) . рования Берлекэмпа, разработанного

Если число ошибок в кодовом слове первоначально для обычного цикличесне превышает половины исправляющей кого кода полной длины. Реакльный способности кода, то они могут быть код не является таким кодом, поскольисправлены обеими "половинами" деко!

5 ку он получается укорочением дополнидера (2,4,6 и 3,5,7). В накопители тельного циклического кода полной

13 и 14 поступит при этом одинаковая длины. Поэтому для декодирования информация, которая через элемент ИЛИ реального кода можно использовать про(S подается на выход 26. Данный ва- цедуру декодирования дополнительного риант в случае появления ошибок наи-. кода, у которого крайний проверочный более вероятен, поскольку. ошибки боль- символ будем считать стертым 3 . шей кратности обычно происходят реже, Алгоритм декодирования реального а вероятность сбоя фазы значительно (и, К)-кода, основанный на алгоритме меньше вероятности обычной ошибки декодирования дополненного (n+1,K)символа. кода, у которого крайний стертый проЕсли число ошибок будет также не- верочный символ будем считать первым велико, но в канале появится одиноч- по счету, удобно представить в сленая ошибка, вызванная сбоем фазы, то дующем виде. блоки 3,5,7, оперирующие с фиктивным

Алгоритм Х

1. Вычислить взвешенные степенные большой вероятностью на выходе блока симметрические функции 8 (, S Z. ° ° » Sg > в+4

7 будет сформирован сигнал "Ошибка", от локаторов искажений S. .О х . который через элемент ИЛИ 16 произве.(i=2 дет сброс третьего накопителя 14. Многочлен локаторов стиранийЛ=1+к z

Происходящий при этом переброс триг- 2. Определить многочлен T(z) гера 20 не приведен к формированию

35 б(-! сигнала "Ошибка" элементами 22, 23 1 + Т„z (1+ Е.Б„z 1Л и 17, если не будет переброшен тригк=> гер 19, Блоки 4 и 6 произведут в сум- Решение ключевого УРавнениЯ маторе 8 исправление ошибок вместе с (1+ — Т "- ) + () () (z)j А ошибкой фазы и исправленная информа- 3 К = 0 rh 0 1 c 1 D(0)

° р р ция из накопителя 13 постУпит на вы- В(0) 0 исходнь,е данные ход 26 к потребителю.

4. Определить Л., — коэффициент при к

Если число ошибок кодового слова I превысит половину исправляющей спо- 45 z "+ в многочлене ((+ .ЕТ«>г ) (г) . собности кода, но не превзойдет «пг последнюю, то блоки 4 и 6 не смогут 5. ВычислитьЯ"" = Q + 6" "z ( исправить последовательность ошибок 6. Т известно? Нет — пер.11.

H сформированный с большой вероятно- " E,r y, 0(V(D K

1l !> стью сигнал Ошибка на выходе блока -1 - 2 .

6 произведет сброс накопителя 13, а бб т тз д Г > +>(((> б) исправленная информация с накопителя (-((2 1

14 поступит на выход 26. true, то - пер.8. иначе - пер.Я.

Одновременный сброс накопителей 8. D(K+1) =D(K); B(K+1) =B(K) l

13 и 14 и формирование сигнала "-"шиб- ъ(1= г >. . Пер.10. ка" на выходе элемента ИЛИ 1 7 прои- 55 9 ° D (K+ 1 ) * К+ 1 — D (K) В (К+ 1 ) зойдет в декодере в двух случаях: если сигнал "Ошибка" возникает в обо- . 6.(<) их блоках 6 и 7 — через элемент И 22, - 10. К, = К+1 Пер ° 4.

I и при появлении сигнала несовпадения Вычисление и исправление ошибок

1599996

Д-1

11. 9 (z) = z ..

«=о

12. j:=1 (поскольку первый символ дополненного кода, для которого j = 0 5 отсутствует). 6 5 4 3 2 ь- акоп 1 1 1 1 1 1 1 .1

01 1 100, 0

55 (1) 1 1 1 1 1 1 1 (9 1) = 0? Да — ошибка. Пер.6.

14. j: = 3+1

15. 1 и + 1? Да — пер.20. Нет — p пер.13.

16. ф (г):

1+ г

17. Исправление ошибки.

18, Я(г) = 1? Нет — пер.13. 15

19. Ошибки исправлены.

20. Неисправляемая комбинация ошибок. . При этом раздел алгоритма 1 "Решение ключевого уравнения" (блоки 3- Zp

10 алгоритма) реализуется в блоке 4 декодера, а раздел "Вычисление и исправление ошибок" (блоки 11-20) алгоритма — в блоке 6 декодера.

Рассмотрим особенности выполнения блока 2, в котором реализуется блок 1 алгоритма 1. Для декодирования обычных циклических кодов по процедуре

Берлекэмпа степенные симметрические. функции S вычисляются следующим об- 3р

J разом.

1. Производится вычисление остатка от деления принятого кодового слова

R(x) на минимальный многочлен М(Ы1) элемента расширенного поля Галуа р .

2, Выполняется преобразование остатка в соответствии с процедурой

"матричного умножения" (поясняется ниже на примере).

Для рассматриваемого реального кода, не являющегося циклическим, эта процедура требует модификации, которую только для удобства изложения рассмотрим на примере простейшего реального (6,3)-кода, для которого 45 р . — корень неприводимого многочлена..

Одновременно, только для этого примера порождающий многочлен фиктивного (7,4) — кода g (х) = х + х + 1.

Проверочная матрица дополненного (7,3) — кода имеет вид

К подматрице матрицы (1) размерности 6 х 3, отмеченной пунктиром, следует привести проверочную матрицу реального кода с целью применения блоков 3-20 алгоритма 1 декодирования.

Поскольку линейная операция над строками проверочной матрицы линейного кода приводит также к проверочной матрице, то сложение последней и предпоследней строк матрицы I для удаления правой "1" в предпоследней строке приведет также к проверочной матрице дополненного кода, удаление правого столбца и нижней строки которой приведен к матрице реального кода

101110 (2) H = 1 1 1 001

100011

Матрица (2) отличается от выделенной подматрицы матрицы (1) только инверсией нижней строки, поскольку нижняя строка "единиц" матрицы (i) является проверкой на четнбсть. Для того, чтобы получить необходимые для декодирования степенные симметрические функции S< в виде линейных комбинаций столбцов выделенной подматрицы матрицы (1), нужно в процедуре вычисления функций S< просто повторить вышеприведенные операции с матрицей НА и

4оп получится процедура вычисления степенных симметрических функций S в следующем виде.

Пр оцеду.ра 2,.

1. Умножение многочлена принятого кодового слова на "х" (с целью присоединения" отброшенного символа дополненного кода) °

2. Получение остатка от деления на минимальный многочлен М(Ф").

3. Вычисление четности, например, делением на двучлен (х+1).

4. Добавление четности по п. 3 к младшему разряду остатка по п.2.

5. Если остаток не равен 0 и четность равна 1, то — инверсия младшего разряда остатка (модифицированного по п. 4).

6. Преобразование результата процедурой матричного умножения".

Проиллюстрируем применение алгорит. ма 1 и процедуры 2 в полном объеме. на примере реального (30, 15) — кода, которому соответствуют фиктивный (31, 16)-код, имеющий минимальный вес йд„„ = 7 и дополненный (30,15)-код с dù „= 8 с проверочной матрицей

9 1599996 10 30 29„ 26 гт 26 гк 24 29 гг 7< го, <9 <6 \т <64 <99 <49 <9 <29 «9 <о„9 B+7 6 B ° з 2 29 гт 29 1 29 2< <9 <т <9 << << 19 Г 9 9 1 30 269{26 244ггг 20 <В <6 <4 <2 <0 6+6+4+2 t{ 2B „26 22 <9 <6 <9 <О 7 4 29 26 23 20 (<7 <4 << 6 (3 2 (З<<К27М 24 (г< (М (<Ю <2 9 6 (3

К К 0 27 29 <9 <6 «7, З,„зо {26, 22 <г <4,„«г уб{2 29 гз 2< {97 <9 9 З { <28 24 г<г <6 { <2+B+4 1{ г,ов

26„2«6 «6 гт 22 <т <2 т 2 гь гз, <69 <9, ю 96 29О 24 <99 <9 9 4 зо л9 29 «9{<9 6 1! ® 2% <Ч )о(7О„26 9 29 <4 8 2 27 2< 1Я 9 9 22 22 16 <р 9 г9 29 97 << B 9<< 24 <2 <2,6 1{

1 l { { { { { { { { { { { { { где (для этого примера) o(, — корень минимального многочлена М(2Д =х +х +1.

6 2

Кодирование следует производить путем приписывания к передаваемой информационной части слова п — К + 1 = 16 15 нулей, деления на порождающий многочлен реального кода g (х) х + х +

16

+ х + х7 + х + х + x + 1, отбра7 6 5 Ф сывания младшего проверочного разряда (степени х ) и вывода оставшихся 20 и-К = 15 символов в качестве проверочной части кодового слова. Многочлен

g (х) =, (х+1) -g (x), где @,т(х) - по-. рсждающий многочлен фиктивйого кода, @(х) = M(a) ° И(М ). И(сг ), в котором

M(a) =x +х +х +х +1, М ({«, ) = х <. х + х + х 4 1. Отметим, что элементы 2-ой, 4-ой и 6-ой

I строк матрицы (3) являются четными степенями соответственно элементов 30

1-ой и 3-ей строк, не нужны для апре деления кода данного примера и включены в матрицу (3) лишь для удобства пояснения процесса декодирования.

Степенные симметрические функции 35

S, определяемые в п. 1 алгоритма 1, представляют собой сумму элементов

j-и строки матрицы (3), соответствующих искаженным при приеме символам кодового слова, Для нахождения степенных функций применим процедуру 2, в пунктах 1-5 которой для S1, S<, S г будет использоваться г (К) — остаток от деления

< на И(Ф) = х + х + 1, для Sgu S6 — 45

<9).

r (, Ы ) — остаток о т деления н а M (,eC ) и для S — соответственно r (0 ) .

Ю 5

В процедуре матричного умножения по и. б матрица, используемая для получения S, оказывается единичной, поэтому S9 просто совпадает с "пятибитом" (для данного примера), полученным в п. 5. Однако, вычисление

Sz — S{, требует более сложной схемы.

Схемы связи для этих матриц умножения получаются из правых пяти столбцов расширенной матрицы Нд,<т(3) в которой столбцами показаны двоичные (пятиразрядные) эквиваленты элементов Ы

{ { { { 1 9 { { 9

В табл. 1 показаны матрицы умножения для 6-го этапа процедуры 2 вычис,ления степенных сумм S 1 — S <, Благодаря такому выполнению по и 1 алгоритма 1 проверочная матрица реального кода для целей декодирования получается в виде отмеченной пункти-, ром части матрицы (3), т.е. беэ столбца и строки, состоящих их единиц.

В табл. 2 представлены результаты этапов выполнения процедуры 2 вычисления функций S при искажении в приниЭ маемом кодовом слове 5-го символа справа (степени х, поскольку в прка нимаемом кодовом слове правый бит соответствует нулевой степени многочлена) .

В табл. 3 -приведены результаты этапов решения ключевого уравнения для реального кода по алгоритму 1 при искажении в принимаемом блоке первого и второго символов справа (х+1).

В результате решения ключевого уравнения алгоритм i в данном примере переходит к п,. 11 с ф (х}=*1+р Ъ +

+ о(С = (1+ pCz)(1+ {9< z). Дальнейшее выполнение алгоритма 1 приводит к исправлению двух ошибок при следующей последовательности операций с указанием их результатов в угловых скобках

12» . j=i 3; 13» )1(Ы } =* 07;

16»- g (z) = 1+ p{ z >; 17; 18; 13<

»Ъ ({<< ) г 0); 14» j 2); 15; 13(» ({<4 ) = 07; 16» g (z)=1); 17; 18;

1 т.

Для рассмотрения принципов работы блоков 3,5,7 при декодировании фиктивного кода вернемся к простейшему примеру реального (6, 3)-кода, для которого желательный (в целях удобства декодирования) вид матрицы фиктивного (7, 4)-кода будет матрица (1) без нижней строки единиц. Если воспользовать-. ся формулами преобразования проверочной матрицы фиктивного кода в проверочную матрицу реального кода

) 3 .{ а Ь а + Ь (j 2n) (5)

11.

1599996

12 т (1 где а, Ь вЂ” соответственно i-е столб- в процедуре вычисления функций повтоцы проверочной матрицы реального и рить приведенные операции для полуфиктивного кодов (при этом, имеем так- чения матрицы (8) и получится процеже соотношение для матрицы фиктивного дура вычисления степенных симметрич5

1 кода ных функций 81 в следующем виде и+ ь = Co)

Процедура 3

1 — 1. Умножение многочлена принятого кодового слова на х2. Получение остатка от деления на многочлен (х+1) М(о().

3. Удаление младшей компоненты остатка (степени x ), уменьшение на 1 степеней остальных компонент остатка.

4. Выполнение преобразования полученного синдрома (остатка) $

Ь,= УВ (9)

J I

1

1 20 1 последовательно, с ростом 1, где m —, степень минимального многочлена М(оС ).

5. Преобразование результата процедурои матричного умножения" аналогично процедуре 2.

Вычисленные с помощью процедуры 3 симметрические функции могут быть использованы для обычной итеративной

Например, из верхней части матрицы (1) получим проверочную матрицу реального кода

1 1 0 I 1 0

Н =- 1 01 i 1

P I

010 I 11

110 100

111001

40 (8) Н

P где 0 — пулевой вектор) и если матрица фиктивного кода представлена в 10 каноническом виде, т.е. правая подматрица размерности (п-К) ° (и-К) представляют собой единичную матрицу I то в правой части матрицы реального кода получим после преобразования (5) IS подматрицу вида

Поскольку линейное преобразование над строками проверочной матрицы линейного кода приводит также к проверочной матрице, то в матрице (7)

1 можно заменить вторую строку суммой первой и второй строк, .а затем 35 третью строку — суммой трех строк. В результате получим проверочную матрицу в каноническом виде

С другой стороны, i-й столбец матрицы (8) можно получить с помощью 45 следующей процедуры:

1. Приписывание "Ои справа к принятому слову (умножение многочлена принятого слова на "х");

2. Получение остатка от деления на 50 многочлен g>(x) = g+(x) ° (х+1) =

=(х + х + 1) ° (х+1)=х + х, + х + 1.

3. Удаление младшего символа остатка.

Для того, чтобы получить необходимые pëÿ декодирования в фиктивном коде степенные симметрические функции Si в виде линейных комбинаций столбцов верхней подматрицы матрицы (I), нужно процедуры декодирования, в частности, может быть использован .приведенный выше алгоритм 1, в котором операция

12 заменена следующей: "12.j:=0", алгоритм 1 со скорректированной операцией 12 назовем "Алгоритм 1а".

Проиллюстрируем применение процедуры Зи алгоритма 1 g в полном объеме на примере реального (30, 15)-кода, которому соответствует фиктивный (31,16)-код, имеющий проверочную матРицу (3) с удаленной нижней строкой

"единиц".

Пусть на блок 3 поступает нулевое кодовое слово с искаженным пятым и шестым символами справа (двучлен

x + х ). В табл. 4 представлены ре4 5 зультаты .этапов выполнения процедуры

3 вычисления функций S ..

Отметим, что на этапе 2 процедуры

3 вычисляются остатки от деления на мн: гочлен (х+1) М(р) = x6 + х + x +

+ х + x + 1 для 1-ой, 2-ой и 4-ой строк, (х+1) И(о() = х + х + х +

3 6 2для 3-ой и 6-ой строк и (х+1) М() =

5 б э

=х +х +x +1для j: îéстроки матрицы (3) .

Вычисленные значения образуют в матрице (3) шестой столбец справа, ! который .породит единичный импульс исправления с декодирующего выхода блока 7, но на выходе сумматора 10 из- 10000

oL 1 1 000, 1 1 100

1 l1 1 1 1 1 (10) 13 159 за задержки в элементе 12 будут сформированы сигналы для исправления двух соседних символов.

Отметим также, что процедура 3 мо- жет быть упрощена за счет совмещения операций 4 и 5, поскольку преобразование синдрома по формуле (8) может быть выполнено методом "матричного умножения" на матрицу преобразований

9996 14 (2), исправляющего ошибки только в фиктивном коде при условии отсутствия сбоев фазы в кодовом слове.

Обозначим через Р„ вероятность невозможности декодирования слова, пораженного ошибками символов, при условии отсутствия сбоев фазы в канале, под этим будем понимать как отказ

10 от декодирования, так и ошибочное декодирование. Через Р > обозначим ве- роятность сбоев фазы в слове. Ввиду независимости искажений символов и сбоев фазы вероятность невозможности декодирования в (2) будет з хххх1

Согласно математическому определению матрицы последовательное выполнение двух матричных преобразований можно заменить одним преобразованием в соответствии с матрицей — произведе. нием двух частиц.

В качестве примера для оценки зф- фективности изобретения рассмотрим двоичный (63, 33)-код, порождающий многочлен которого не содержит умножителя х+1 (злемент показателя 0 не является корнем многочлена) и минимальный вес которого d „„ 11. Такой ход может быть фиктивным (п = 63), а реальный (62, 32)-код, у которого и, = 62, также имеет д„д = 11 и может исправлять до = (с1ми„ -1)/2=5 ошибок.

По фиктивному коду декодер (блоками 3,5,7) исправляет до 5 ошибок битов, но без сбоя фазы. По реальному коду декодер (блоками 2,4,6) может исправлять не более двух ошибок символов, поскольку каждое искажение

I ошибочного символа в канале дает в результате сдвоенную ошибку в приемнике ОФМ. Однако, декодер по реальному коду может в кодовом слове длиной 62 бита исправлять одну ошибку фазы и до двух ошибок символов или 2 ошибки фазы и одну ошибку символа (пренебрежем появлением большего числа сбоев фазы в слове, чем лишь занизим исправляющую способность декодера) .

Пусть в канале вероятность искажеl ния символа P см=5 10, а вероятность сбоя фазы на данном символе Р< фаз = — 10, причем искажения символов и сбоев фазы распределены случайно и независимо друг от друга. Рассмотрим сначала возможности декодера аналога

Р = 1 — (1-Р )(! -Р„,), (11) где P = 1-(1-P

ДлЯ вычислениЯ" Ря УДобно воспользоваться формулой

Nq)47 i + и +9 в которой достаточную точность расче25 та можно получить при использовании первых четырех слагаемых по знаКам суммы,,„. = 5.

Для данного примера Р = 0 00618, а Р нЗс = 0$826 10 е из значит ьного

30 превышения Р р над Р „, видно, что исправляющая способность кода недоиспользуется за счет невозможности исправления в прототипе сбоев фазы. Поскольку Р >т Рн с, подстановка этих значений в (11) даст Р„ - P

35 = 0,00618.

Для предложенного декодера с целью учета рассмотренных выше возможностей блоков 2,4,6 из рассчитанной величины P„> следует вычесть поправку Р с, формула для которой получается в виде

\ч -1

Расчет по формуле (14) даст Р

= 0,616.10 а разность Р„-др

= 0,00002 показывает, что верхняя: оценка вероятности ошибочного декодирования предложенного декодера по-. лучается для параметров. данного при55 мера на 2,5 порядка ниже, чем для аналога 12).

Теперь предположим, что в декодере циклического кода прототипа Я реализован рассматриваемый (63,33)-код

15 .599996

Боуза-Чоудхури. Ксд может гарантированно исправлять t* = 2 пары ошибок, I но исправлять 3 пары ошибок в общем случае не может.

Подставляя в формулу (13) значения и = 63 и t* = 2 вместо соответственно п и t получим для прототипа при использовании первых двух ! слагаемых под знаком. суммы величину

Р н = 0,00385, которая заведомо меньше результата использования всех слагаемых формулы (13), но значительно больше оцененной выше величины Р„ предложенного декодера, 15

Формула изобретения

Декодер циклического кода, содержащий первый буферный накопитель, вход которого объединен с входом пер- 20 вого блока формирования синдрома и является информационным входом декодера, первый и второй выходы первого блока формирования синдрома подключены соответственно к первому входу 25 первого блока вычисления поправок и к входу первого блока вычисления локаторов ошибок, выход которого соединен с вторым входом первого блока вычисления поправок, первый выход которого и выход первого буферного накопителя подключены к первому и второму входам первого сумматора по модулю два, отличающийся тем, что, с целью повышения достоверности декодирования кода, принятого из канала с относительной фазовой модуляцией, в декодер введены второй и третий буферные накопители, второй— четвертый сумматоры по модулю два, элемент задержки, первый — третий

40 триггеры, первый — четвертый элементы

ИЛИ, первый и второй элементы И, второй блок вычисления локаторов ошибок, второй блок вычисления поправок и второй блок формирования синдрома, вход которого подключен к информацион.-ному входу декодера, а первый и втопой выходы соединены соответственно

16 с первым входом второго, блока вычисления поправок и входом второго блока вычисления локаторов ошибок, выход которого подключен к второму входу второго блока вычисления поправок, первый выход которого непосредст венно и через элемент задержки соединен с первым и вторым входами третьего сумматора по модулю два, выход которого соединен с первым входом вто- рого сумматора по модулю два, второй вход которого подключен к выходу пер вого буферного накопителя, вторые выходы первого и второго блоков вычисления поправок подключены к установочным входам одноименных триггеров и первым входам одноименных элементов

ИЛИ, выходы которых соединены с входами обнуления соответственно второго и третьего буферных накопителей, выходы которых подключены к первому и второму входам четвертого элемента

ИЛИ, выход которого является информационным выходом декодера, входы обнуления первоГо — третьего триггеров объединены и являются входом обнуления декодера, первые выходы первого и второго триггеров подключены к первому и второму входам первого элемента И, выход которого соединен с первым входом третьего элемента ИЛИ, выходы первого и второго сумматоров по модулю два подключены к информационным входам соответственно второго и третьего буферных накопителей и соответственно к первому и второму входам четвертого сумматора по модулю два, выход которого соединен с установочным входом третьего триггера, выход которого и вторые выходы первого и второго триггеров подключены к первому — третьему входам второго элемента И, выход которого соединен с вторым входом третьего элемента

ИЛИ, выход которого подключен к вторым входам первого и второго элементов ИЛИ и является выходом ошибки декодера.

1599996

Та блица а! j 0 3!

О(11 !о

1 !

0 0 0 0

1 0 0 0

0 1 0 0

1. 0 0 0

Из строки 2 матрицы (3) Ь 6 4ь г (ДлЯ 82) Из строки 1 матрицы (3): 4 г (для S,) 0 0

1 0

0 0

1 0

0 0

0 1

1 0

0 0

0 0 0

0 0 0 1

4 3 2 х х х

3 2 х х х 1 х 1 ф6 12. 4

О Ыо

S3) (длЯ S 4) з г х х х х" ххх1

2 (4) х 1

1 1 0 0

1000 (для S ) 6

1 0 1 0

1 0 0 0

1 1 1 1

0 1 0 0

1 1 1 0

0 0 1.

Ф 3 2 х х х х х х 1 х 1

Т а б л и ц,.а 2

S L5 4. S5 86.

М»

Этапы процедуры 2

8г х х х

Умножение на "х"

Остаток от деления на M(g ) х +1

x.+x +х+1 х +х +х +1

0 2 0- 3 2 г. 4 Ф. х. +1 х +х +х + х +I .+1

1 1

Четность

2. 4 2 4 В

x x +x +x х +х +x

Остаток с добавленной четностью з х - х +х +х хг

Г х +1 х +х +х+1 х +1 x +x +х +1 х+х +x +1

2 3 ф 2 4 2

После инверсии младшего разряда х +1 4 + 3+ 4 +g 4 О i = Ф +М М г Э 7 20 с(+1=

q lf о1

К 4Ф+

4 гr

Результат матричного перемножения

Р(+0 "М

Ы +1=И р 11 с !О 0 са 1О

1 О

1 О 0 0

1 1 1 0

0 0 0 0

1 1 0 0

0 0 0 1 м

a 1 р(fO к

11 о(I1

М 11

0(г I 1

< 11

1 0

0 0 1 0

1 1 0 0

1 0 0

1 0 0 0

0 1 0 1

0 0 0 0

0 1 1 0 k Ф a "о

19

1599996

Таблица 3

Результаты этапов декодирования

Этапы

Многочлен T(z) =1+ c» z+a z + ос :: + ос г +Ы. !z + Ы z ,11 )0 2 28 3 !5 4 4 5, . 4 6 уравнение: (!е!! ге!г г +tZzz +Ш г ее zz) !(г)е((г)!той z

О 1 ) 2

4 (), ) (зо

5 (Я ) 1+ сс z о

1+p{ 2+ос z !+ос z + g z

23 18 2 19 3

1+ ос к

6 (уход) Пер.к.п.7

Пер. к п. 7

Пер. к п. 7 Пер. к п. 11

8 (D, В, (. (K+1) ) Нет

Нет

Нет

9 (D, В, с (К1.1)) 1; 1; OC

1; О;

1а+ 15

2; 1; (28+ 26

Таблица 4

4 5 6

l !

Этапы процедуры 3

Х +Х

5 (" х +хб..! и х +х х +x

5 6

5 ь х +х

5 ь х +х р 4 3 5 2 х+х +х +1 х+х +к +1

2 х +х +1

2 х +1 х +х+1

4 З г х +х +х х +х +1 х +х +1

Ф, 4 3 2 х +x +x+1 х+х+1 г

4" 2 4 З 2 х +х +х +1 х +хс1-х +1 х +1

0010 t-=

+x +1 а г+1гг

С)с о 1=

4 3

2в

Ы -о(= 20

+! = lX ()(- +g t cl kg+1z

4 1О < 3 2

g!ð

1 4,(, Зс) Редактор М.. Товтин

Заказ 3151 Тираж 659 Подписное

ВНИИПИ Гос ударс твенного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 1О!

Умножение на х

Остаток от деления на многочлен (х+1) ° М(о1 )

Удаление компонента с х

Преобразование синдрома

"Матричное умножение"

Циклы решения ключевого уравнения (К = 0,1,...) 3 2 3 2 2 3 2 х +х +х+1 х+ х +x+1 x+x+x+1 х+х+х+1

Составитель О, Ревинский

Техрер 11 дидык Корректор Т. 11алий.