Мажоритарное декодирующее устройство корректирующего кода рида-маллера
Патент 902283
Авторы
Классы МПК
Мажоритарное декодирующее устройство корректирующего кода рида-маллера
Иллюстрации
Реферат
Сотов Советскик
Социалистические
Республик
ОЛ ИКАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ()902283
/ д (6 ) Допол н ител ьное к а вт. с внд-ву (5! )М. Кл. (22) Заявлено 1 1.01.80(2! ) 2868586/1 8-09
Н 04 1/10
Н 03 К 13/34 с присоединением заявки №(ееударствапв|И квмнтет
СССР (23) Приоритет ао делам нзсбретеннй н еткрытнй
Опубликовано 30.01.82. Бюллетень №4
Дата опубликования описания 30.01.82 (53) УДК 621.394.. l 4 (088. 8) (72) Авторы изобретения
В. А. Хромушин и М. А. Солодовн
l (1 (7!) Заявитель (54) МАЖОРИТАРНОЕ ДЕКОДИРУЮШЕЕ УСТРОЙСТВС
КОРРЕКТИРУЮЩЕГО КОДА РИДА-МАЛЛЕРА
1 ь
Изобретение относится к радиотехни| е и может быть использовано в системах передачи дискретной информации по каналу с шумами.
Известно мажоритарное декодирующее устройство корректирующего кода Рида(|аллера, содержащее лва счетчика, решающий блок, регистр слвига и сумматор по модулю два, выход которого подключен к информационному входу решающего блока, при этом к информационному входу регистра сдвига подключен выход решающего блока (13.
Однако известное устройство содержит большое количество счетчиков и сумматоров по модулю два, что при большом числе информационных символов приводит к сложной схеме соединений, затрудняюmNx его микроминиатюризацию.
Цель изобретения — упрощение устройства путем сокрашения блоков обработки сигнала и логических элементов, Указанная цель достигается тем, что в мажоритарное декодируюшее устройство корректирующего кода Рида-Малле ра, содержащее два счетчика, решающий блок, регистр сдвига и сумматор по модулю два, выход которого полключен к информационному входу решающего блока, при этом к информационному входу регистра сдвига подключен выход решающего блока, введены последовательно соединенные формирователь строб-импульса и коммута= тор, а также запоминающий блок, выход то которого подключен к управляющим входам коммутатора, к лругим входам которого подключены выходы регистра сдвига, а выходы коммутатора подключены ко входам сумматора по молулю два, при
15 этом ко входам запоминающего блока подключены BbKollbI последовательно соединенных первого и второго счетчиков, причем тактовый и установочный входы первого счетчика объединены аоответст
20 венно с тактовым входом решающего бло ка и установочным входом формирователя строб-импульса, ко входам которого подключены выходы второго счетчика, вход
902288 которого обьединен с тактовым входом регистра сдвига.
На чертеже представлена структурная схема ItpeanaraeMoro устройства.
Устройство содержит запоминающий блок 1, коммутатор 2, сумматор 3 по модулю два, решающий блок 4, регистр
5 сдвига, счетчики 6 и 7, формирователь 8 строб-импульса.
Устройство работает следующим об- 10 разом.
Коэффициент пересчета счетчика 6 выбирается равным минимальному кодом-3 вому расстоянию d 2 > где и =- 3— любое целое положительное число; < I5 порядок кода, Коэффициент пересчета счетчика 7 выбирается равным количеству инЯ формационных разрядов k 9И1
Число разрядов регистра 5 сдвига вью бирается равным К - числу информационных разрядов корректирующего кода Рида Маллера.
Рассмотрим работу схемы на примере кода Рида-Маллера второго порядка (5 g), имеющего длину It= 32, количество информационных разрядов К = 16 и мини« мальное кодовое расстояние d „и =8.
Данный код может обнаруживать ошибки кратности с = 4 и исправлять ошибки кратности Ф4 « 3.
Код Рида-Маллера, поступающий на вход декодирующего устройства образуе тся с помощью производящей матрицы 6, имеющий вид .
1 1 1
1 О 1
1ОО
011
0 О О
О О О
1 О О
001
О О О
О О О
000
11111
0101О
I I 001
1 1 О О О
О О 1 I 1
С 001 0
0000 О
О О О О
ОООСО
О О О О О
0 0 О О 0
1 1 1 I 1 1
О 1 О 1 О 1
1 1 О О 1
О О 1 1 1 1
О О О О О О
1 1 1 1 1 1
О 1 О О О 1
О О О 1 О
О О О О О О
0 О О
О О О О I 1
О О О О О О
О О 1 I
О О О 0 О О
О О I 1 1
О О О 0 0 О 4 П Ц 4ЦП! U +U ци U„z g> U> U 0 U,! О., Ц„О„Цд, Ц„ц и и О, О, 1 „О О„О, О
Ф где Х, Х„, Х Хз Х4 ° Х9, Х . Х Х Х, ..., Х4, Õ -строки ироизвоця цей матрицы; с!. с ... а - информационные символы, г..-> ьподлежа щие кодированию
U 0 . U — символы кола, получен3. " 3 ные в результате кодирования.
Кодирование информации осуществляется путем суммирования по модулю 2 тех информационных символов, которые соответствуют единицам в столбцах производящей матрицы:
40 Jt
U !.
U3 о„ и
Оь
Uv
Us
9
UIO = и, U„=
043
Ъ =
UIg =
uI(1-!!7 = а„ а,+ а1+
aI + а + а„+ а„+ а1+ а, + а„+ а + а!+ а,+ а а, +
aI + а„+
a + а4 а4 + ао а!! а+а+а+а8+а1„
9 9
9+ а,+ а9+ ау+ ац а, I- а!.+ а„+а+ а+ ач+
3 а + а9+ а, а„,+ а,„+ а„, а + а + а + а + а„+ а„+ а!, 8 9
О 1 О
О О
О О О
ООО
О 0,0
ООО
О О С
° О 0 О а„ аз а„+ а> а + аз+ а„+ а а +
Ь а + з а + а4 а„+ а 3 с. y + аь
1 1 I 1 1 1 1
I О 1 О 1 О
1 О О l 1 О О
О 1 1 1 1 О О
1 1 1 1 О О
О 0 О О 0 1 ! О О О 1 О О
О 0 I О 1 О О
1 О 1 О 1 0 О
О 0 О О 0 О 1
О О О 1 1 О О
1 0 О 1 1 0 О
О О О О О 0 О
О 1 1 1 1,0 О
О О О 0(I О О 0
О О О О О О О
l 1 1
О 1 О
О О 1
О О О
1 1
1 1
0 О О
О О О
О 1 О
О 1 О
О О О
О О 1
О О 1
О О 0
О 0 О
1 1 1
1 1 1
1 О 1 О
О О 1
О 1 1 1
I 1 1
t 1 1 1
О О О
О О t 0
1 О 1 0
1 О 1 О
0 0 О 1
1 О 0
1 О О 1
О 1 1
О 1 1 1
1 1 1
1 4 а, 1 Хл эр
1 Xt ° ээ
1 Хв эа
Х4 Э5
Х;Х Х, 1 Х ХЭ ЭЭ
1 )4l Xl, э
l Х Х9 Э
Хр Хь
Х Х„Э
1 Х Х э, 1 " Хq Х,, а„, 1 ХЭХЭ
x„„x !
902283
Проверочные уравнения находятся из производящей матрицы G. Принцип поиска проверочных уравнений заключается в нахождении таких совокупностей столбцов, сумма которых по модулю 2 будет 50 содержать только одну единицу в разряде, соответствующему отыскиваемому информационному символу V.
Каждый информационный символ может быть описан не менее чем d a„не- 35 зависимыми проверочными уравнениями, аргументами которых являются символы
О, кодового слова. Анализ результатов решения этих уравнения по принципу большинства позволяет определить значе- В0 ние информационных символов Зл.
Для рассматриваемого примера существует следующая система проверочных уравнения:
О +
Олв + 4ь
Ua + Оло+
U> + U« + 4 +
О В + ЦгЧ
Оао + Огв
О + Огв ль
U3 8
ОЬ + Е,„+
"aa + Озв аз и а4 ЗВ
ОВ + 0
"а + Оль+
0« = а + а + аь+ a„ù, -U„= а„+ а + аь+ а„, U = ал + ав+ a3+ аь+ a + ало+ а 3
Овл = a(+ a4+ as+ а е
Оц = ал+ а + а4+ аЬ+ ав+ а„+ а,с
01 — — а„+ а + а4+ аь+ а„+ ае+ а,с
utk — — а, + а + a3+ ал+ as+ а + a8+ a%+
Ua5 = а, + as-+ аь+ ass
ОА6 aq а + ас аь ав а10
Uay = ал + аз + ас+ as+ a< + ay+ э», Uas = ал+ а4+ ас+ аь+ а + a< + аль
Uas = ал+ ав+ а4+ àс+ aь+ ав+ аВ+ аю+
Цзл а + аз+ ал+ ас+ аь+ аю+ a„+ Q+
О = ал+ а а + а.„+ а + аь+ а + ав+ з л а ю ь с ° т где + — знак суммированных по модулю 2.
Закодированная информация U„, Ц, „U через канал связи поступает на вход 1 20 декодирующего устройства.
Декодирование информации осуществляется путем решения системы проверочных уравнений.
a„„+ a„+ a„ а,+ а„,+ а а„+ а,+ аль а„+а+аь а + а + а„+ а + а + а + а„ + а
Олл +
Олс +
Оль +
Оло
О
0„
Ол
+
О, 03
ЦЧ
О, U
03
0>
Ug
ОЧВ
u„
ЦВ
Оь
U, +
ОВ + 4 +
ОМ +
О +
0,4 +
ЦВ +
Ол +
0s +
0å +
0„+
0 +
ОМ. +
+
+
+
+
+
+
Олб +
Ов +
0„+
Ог
Цлв +
ОВо +
ОВ +
Ua4 +
+
+
+
+ лч
О, О, Us
Цв
U„
u„
u,„
О, +
Uag +
U +
О в +
О,, +
0<Â
Це +
Uao +
05 +
Олв +
Олл +
0<+
Ъ+
ОВЬ +
U +
U +
Олв +
Ов+
Ъ+
Ua(+
ЦВ5.+
Uas+
Ua9+
Ufo+
Ug +
О, +
Олв +
Ол +
Usg +
Оа+
ОВВ +
U +
Ua
Ом
0„
О„
ОВ
Uas
u„
Ол
Ол
Олс
U»
ЦВ
U„
Озл
0ВВ
Мл5
Uao
ВЗ
41.
Ов
ОВВ
Ол
0, Цм
u„
Us
О«
Ъ
Огв
Оъ
90228Э
О», О в +
+
+ "а
+ ОФ
u» +
1»р
03 +
09 + Олл +
О, + 01» +
U1, + Олв+
5 !
U, + Ug,+
014
+ u16
09 + uzq + 6 лл
»3
+ 0»о+
1»с + ло!
»о + !лу
1»3 + !.13
0»9 +
Ъв+
Uf +
О» +
u„+
Ug +
033 + 0„
0+ 03
U13. + 0»в
U4 +
UU3
03 +
019
+ u»0
Ог +
+ Огг
02Ä
Оз +
0»3
+ u„u
+ 01» + 13 + 11»
U3 + U, + 11
9 + 14
44
1»6 го
06 + 014+
U»5- + 4 +
Ол» +
01 +
u,„
О„+
0 +
u„+
+ 03»
+ 010
u„+
u„+
0»3 +
25
U3 +
+ u„, U» + Оь + 1в
uf3
+ URu
u, +
u1s +
+ 016
u»s
0,3 +
u9 +
0}5. + 0»6
0» + 0»8 огл + зо
U1) +
U4 +
019 + 0»о +
Ов +
010 + 014 +
"»3 +
01 +
Олл +
u1 +
Ог +
+ Оь
Нг +
+ 08
+ О
U3
Uu +
Оло +
От
013
1 !
1»
03 +
09 +
9 ! = 013.+
Об +
u„+ 01» +
1, + 1»л
019 +
U8 +
1Ф 017 +
Олв +
0»о +
»3
+ U»»u
1 + 11
1»л + 1»!»
URO +
U3O
+ О
0»в
03, 45
R3 + U15- +
+ Ос
+ Uu + О»
+ U4
+ 08
+ U»»
О, Uð
Олл
U3
+ U6
+ Оло
u10 +
09 +
I — U13 +
+ U16
""6
+ Олг
+ 0»о
+ 0}u
0»3
+ 028
+ 03}, Огэ
U3, U»3 + U»4
О, + 0» + 0»»+ 0»и
+ "ло + 0»,+ 0»ь
0„, + О„+ u„„+ О
013 + 014 + 0»9 + 03о
Огл + Огг + 0»9 + 03о
+ U31 + 03»
Огг+ 0»6 +
О + О„+
+ U» +
+ U6+ лэ+ 018+
+ 0»г+ г + 0»6 +
»9+ 03о +
09
О
О, u4R
U» +
U3+ и, U40 +
011 +
01 +
U3
U4 +
О,„+
11„
1„
+ 1лл
18 + 111 !
»1 +
В
+ 1
+ !»о
+ Ii + 1в
+ 1 + 19
+ !В+ !9
9022
Ua + 13, 1 3 + 5
Ur + 1м
u, +
О, + 14
1О з + IÌ+ Iì
ufo + Ii + If+ II, На вход Щ устройства декодирования подается сигнал "Установка, который сбрасывает в нуль счетчики 6 и 7 и ус- 15 танавливает формирователь 8 строб-импульса в исходное состояние.
Формирователь 8 строб-импульса в исходном состоянии дает разрешение на прохождение сигналов со всех разрядов информационного входа l через коммутатор 2 на вход сумматора 3 по модулю два и запрещает прохождение через коммутатор 2 информационных выходов fV.
Постоянный запоминающий блок 1 дешифрирует нулевое состояние счетчиков
6 и 7 и выдает код на вход коммутатора 2, разрешающий первой группе информационных разрядов входа 1 подключиться к сумматору 3 по модулю два, для рассматриваемого случая при нулевом такте 1, 9, 17 и 25 разряды подключаются к сумматору 3 по модулю два, где происходит их суммирование. Таким
35 образом, решается первое проверочное уравнение.
346= U1+09 ФUA+Уа5
Аналогично, с поступлением тактовых импульсов, происходит решение семи про4О
Первый тактовый импульс поступает на вход П и записывает результат реше» ния первого проверочного уравнения с выхода сумматора 3 по модулю два в регистр решающего блока 4, Одновремен45 но содержимое последовательно соединенных счетчиков 6 и 7 увеличивается на
1. Состояние счетчиков дешифрируется и на вход коммутатора 2 из постоянного запоминающего блока 1 поступает код, разрешающий второй группе разрядов информационного входа I подключиться к сумматору 3 по модулю два.
Таким образом, решается второе проверочное уравнение.
Зь=1)а, О +О, 83 1О верочных уравнений и результаты помещаются в регистр решающего блока 4.
Седьмой тактовый импульс записывает решение восьмого, последнего для 3„ Ф проверочного уравнения в регистр решающего блока 4 и подготавливает решение
4 первого проверочного уравнения для 3„, Окончательное решение о значении принимается по принципу большинства на основании результатов решения восьми проверочных уравнений в решающем блоке 4. Зля этого блок взвешивания кодов решающего блока 4 преобразует число единиц, записанных в регистре решающего блока 4, в двоичный код.
В блоке сравнения кодов решающего блока 4 производится оценка полученного кода.
Если кодовая комбинация на входе
1 не содержала ошибок, то решение восьми проверочных уравнений дает одинаковый результат и в регистре решающего блока 4 будут записаны восемь "1" или восемь 0 в зависимости от передаваемой информации. При этом окончательное решение принимается по принципу большинства.
Если произошла однократная ошибка, например, в 1 разряде, то проверочное уравнение для 3, в которое входит Ц,, будет решено ошибочно. Однако остальные семь проверочных уравнений для 3 будут решены правильно, так как () в них не входит. Следовательно, в решающем блоке 4 будет принято правильное решение.
Аналогично, если произошла двухкрат-. ная (трехкратная) ошибка, то два (три) проверочных уравнения будут решены ошибочно. Однако по принципу большинства будет принято правильное решение.
Если произошла четырехкратная ошибка, то четыре проверочных уравнения будут решены неправильно и по принципу большинства нельзя принять правильноерешение. Четырехкратная ошибка не исправляется, но обнаруживается в блоке сравнения колов решающего блока 4 и вырабатывается сигнал ошибки, поступающий на выход V.
Тактовый импульс, поступающий с выхода счетчика 6 записывает результат декодирования с выхода решающего блока
4 в регистр 6 сдвига.
Аналогично декодируется 3и-, 3„>
3, 3> . Отличие состоит лишь в том, что для каждогс 3< существуют свои проверочные уравнения.
1 1 9022
Декодирование j 3, ..., J, )g базируется на использовании ранее вычисленньм значений 3<, При переходе к вычислениям 3, ..., состояние счетчика 7 дешифрируется в формирователе 8 строб-импульса и триггер формирователя 8 строб-импульса опрокидывается и до окончания цикла декодирования 16, 24, 26, 27, 28, 29, 30, 31 и 32 разряды входного кода 1 10 от сумматора 3 по модулю два и полключает вместо них 2, 3, ..., 16 разряды вьмодного кода Р/. йекодирование 3<, 3, ..., 3<,3 осуществляется аналогично J ...„ )„- в соответствии с системой проверочных уравнений.
Конструктивно декодирующее устройство может быть выполнено на серкйно 20 выпускаемых микросхемах малой и повышенной степени интеграции.
Формула изобретения
Мажоритарное декодирующее устройство корректирующего кода Рида-Маллера, содержащее два счетчика, решающий
83 12 блок, регистр сдвига и сумматор по моaye два, выход которого подключен к информационному входу решающего блока„ при этом к информационному входу регистра сдвига подключен выход решающе- гоблока, отличающееся тем, что, с целью упрощения устройства путем сокращения блоков обработки сигнала и логических элементов, введены последовательно соединенные формирователь
h строб-импульса и коммутатор, а также запоминающий блок, выход которого подключен к управляющим входам коммутатора, к другим входам которого подклк чены выходы регистра сдвига а выходы коммутатора подключены ко входам сумматора по модулю два, при этом ко входам запоминающего блока подключены выходы последовательно соединенных перво го и второго счетчиков, причем тактовый и установочный входы первого счетчика объединены соответственно с такто вым входом решающего блока и установочным входом формирователя строб-импульса, ко входам которого подключены выходы второго счетчика, вход которого объединен с тактовым входом регистра сдвига.
Источники информации, принятые во внимание при экспертизе
1, Авторское свидетельство СССР
Мо 415819, кл, Н 04 L 1/10, 1971 (прототип) .