Устройство для декодирования двоичного линейного кода Советский патент 1986 года по МПК H03M13/15 

гяобретение относится к высилительной технике и технике передачи данных и может быть использовано в цифровых системах передачи информации , Цель изобретения - повышение достоверности передачи или хранения информации. На фиг, 1 представлена функциональная схема устройства; на фиг. 2 схема кодирующего блока; на фиг. 3 схема генератора вспомогательных последовательностей, Устройство для декодирования двоичного линейного кода содержит первый 1, второй 2 и третий 3 регистры, кодирующий блок k 5 первый 5 и второй 6блоки сумматоров по модулю два, блоки 7-10 ключей с первого по четвертый, первый 11 и второй 12 ключи, пороговые элементы 13-16 с первого по четвертый, генератор 17 вспомогательных последовательностей, первый 18 и второй 19 элементы ИЛИ, блок 20 элементов ИЛИ,,первый 21, второй 22 и третий 23 триггеры. Информационнь е входы первого 1 и второго 2 регистров являются соответствующими информационными входами 24 и 25 устройств выходы разрешения записи регистров 1 и 2, управляющий вход четвертого блока 10 ключей, вход установки в ис ходное состояние генератора 17 и вхо ды установки в ноль триггеров 21 23 объединены и подключены к входу 26 стартового сигнала. Выходу первого регистра 1 соединены с первыми ин формационными входами первого 7 и второго 8 блоков клгочей, выходы вто.рого регистра 2-е вторыми информационными входами этих же блоков 7и 8, Управляющие входы блоков 79 объединены со счетными входами генератора 7 и первого триггера 21 и подключены к выходу первого элемента Ш1И 18, первый вход которого является тактовым входом 27 устройства. Выходы первого и второго блоков 7 и 8 ключей соединены с первыми входами соответствующих блоков 5 и 6 сумматоров по модулю два. Вторые входы первого блока 5 сумматоров под ключены к выходам генератора 17, выходы блока 5 соединены с первыми информационными входами третьего блока 9 ключей и входами кодирующего блока 4, выходы которого подключены к, вторым входам второго блока 6 сумматоров и вторым информационным входам третьего блока 9 ключей. Выходы этого блока 9 соединены с информационными входами третьего регистра 3, выходы которого подключены к информацион 1ым входам четвертого блока 10 ключей, выходы которого являются информационными выходами 28 устройства. Выходы второго блока 6 сумматоров соединены с входами первого и второго по эоговых элементов 13 и 14 и входами блока 20 элементов ИЛИ, выходы которого соединены с входами третьего и четвертого пороговых элементов 15 и 16, Выходы пороговых элементов 13-16 подключены соответственно к первому и второму входам первого и первому и второму входам второго ключей 11 и 12, выходы которых соединены с входами второго элемента ИЛИ 19, выход которого подключен к входу разрешения считывания третьего регистра 2 и входу установки в единицу третьего триггера 23, выход которого соединен с вторым входом первого элемента ИЛИ 18 и является выходом 29 сигнала окончания декодирования устройства. Выход первого триггера 21 подключен к входу установки в второго триггера 22, выход которого соединен с управляющими входами ключей 11 и 12. Устройство предназначено для декодирования двоичного линейного кода (24,12) (расширенный код Голея). На первый регистр 1 подаются информационные символы, на второй - проверочные. Рз.зрядность всех шин (фиг. .1), кроме выходной шины блока 20, равна 12, для блока 20-4, Пороговый элеь-ieHT 13 имеет порог три, элементы 14 и 15 - норогдва,элемент 16порог один .Блок 20 содержит четыре элемента ИЛИ на три входа каждый. Кодирующий блок 4 выполнен (фиг, 3) на 12 сумматорах 30 по модулю два, выходы которого являются выходами блока 4, а входы подключены к входам блока 4 в соответствии со столбцами матрицы М, входящей в выражение для порождающей матрицы G, которая для кода (24,12) имеет вид G 3jM, где 3 ,j. единичная двоичная матрица размера 12x12; М двоичная квадратная матрица размера 12x12, имеющая, например , вид

100 000 000 000 010 000 000 000

Устройство для декодирования двоичного линейного кода (24,12) работает следующим образом.

512

По приходу стартового импульса на вход 26 в регистры 1 и 2 в направляемом виде записывается соответственно информационные и проверочные символы принятого кодового слова. Кроме того, осуществляются вьщачи содержащихся в регистре 3 информационных символов предыдущего продекодированного слова через блок 10 ключей на выходы 28 устройства, а также производится установка в исходное состояние генератора 17 вспомогательных последовательностей (причем в исходном состоянии на выходах генератора

17вспомог.тельных последовательноетей ошибок получается нулевая комбинация) , и установка в ноль триггеров 21-23, благодаря чему ключи 11 и 12 устанавливаются в верхнее (фиг. i и

2) положение.

На тактовый вход 27 поступает меандр с тактовой частотой, причем фронт первого такта декодирования совпадает с фронтом стартового импульса, а длительность стартового импульса не превышает чувствительности полупериода меандра тактовой частоты. .Этот меандр через элемент ИЛИ

18проходит на управляющие входы блоков 7-9 ключей, а также на счетный вход триггера 21,

В течение первой половины первого такта декодирования сигнал на вьпсоде элемента ИЛИ 18 равен логической 1 (положительный полупериод меандра тактовой частоты). При этом через блок 7 ключей символы с выходов регистра 2 поступают на входы блока 5 сумматоров по модулю два, а через блок 8 ключей символы с регистра 1 поступают на входы блока 6 сумматоров по модулю два. С выходов блока 5 символы поступают на вход кодирующего блока 4, который формирует на своих выходах символы, соответствующие умножению его входной последовательности на матрицу М, Символы с выходов кодирующего блока 4 в течение первой половины первого такта декодирования проходят через блок 9 ключей на информационные входы регистра 3, а также на входы блока 6 сумматоров по модулю два, причем на выходах блока 6 получаются символы последовательности первого синдрома, которые поступают на входы пороговых элементов 13 и 14, и на входы блока 20 элементов ИЛИ.

726

На выходах блока 20 элементов ИЛИ получаются символы последовательност преобразованного первого синдрома, которые поступают на входы пороговых элементов 15 и 16.

Пороговые элементы 13-16 построены таким образом, что на выходе элeмeнta появляется сигнал логического О, если количество единиц среди символов на входах этого элемента превыщает порог, и символ логической 1, если количество единиц на входа не превышает этого порога.

Сигналы с выходов пороговых элементов 13 и 15 проходят на входы элемента ИЛ11 19 через ключи 11 и 12, причем при появлении на выходе элемента ИЛИ 19 логической единицы производится запись в регистр 3 символов с выходов кодирующего блока 4, а также устанавливается в единичное состояние триггер 23, с выхода которого снимают сигнал окончания декодирования, который приходит на выход 29 устройства и на второй вход элемента РШИ 18, в результате чего прекращается прохождение меандра тактовой частоты через элемент ИЛИ 18 и декодирование заканчивается,

В течение второй половины первого такта декодирования, если декодирование не закончено, сигнал на выходе элемента ИЛИ 18 равен логическому О (отрицательный полупериод меандра тактовой частоты),

При этом через блок 7 ключей на входы блока 5 сумматоров по модулю два поступают символы с выходов .регистра 1 , а через блок 8 ключей на входы блока 6 сумматоров по модулю два поступают символы с выходов регистра 2, в резу.пьтате чего на выходах блока 6 по.пучаются символы последователььюсти второго синдрома а на выходах блока 20 элементов ИЛИ получаются символы последовательности преобразованного второго синдро ма. Символы продекодированной информации поступают на входы регистра 3 через блок 9 ключей с выходов блока 5 сумматоров по модулю два.

В начале второго такта декодирования триггеры 21 и 22 устанавливаются в единичное состояние, причем на выходе триггера 22 появляется

сигнал логической 1, сохраняющийся до прихода следующего стартового импульса, и этот сигнал переводит 71 электронные ключи 11 и I2 в нижнее (фиг. 1 и 2) положение. На входы элемента ИЛИ 19 поступают сигналы с выходов пороговых элементов 14 и 16, С выходов генератора 17 вспомогательных последовательностей на второ и последующих тактах декодирования снимаются ненулевые вспомогательные последовательности, при этом в течение первой половины такта декодирования на входы блока 5 сумматоров по модулю два через блок 7 ключей приходят символы с выходов регистров 2, на входы блока 6 сумматоров по модулю два через блок 8 ключей приходят символы с регистра 1, с выходов блока 6 сумматоров по модулю два снимаются символы проверочной последовательности, с выходов блока 20 элементов ИЛИ снимаются символы преобразованной проверочной последовательности, на входы регистра 3 через блок 9 ключей приходят символы с выходов кодирующего блока 4. В течение второй половины каждого текста декодирования на входы блока 5 сумматоров по модулю два через блок 7 ключей поступают символы с выходов регистра 1, на выходы блока 6 сумматоров по модулю два через блок 8 клю чей приходят .символы с выходов регис ра 2, на входы регистра 3 через блок 9 ключей поступают символы с выходов блока 5 сумматоров по модулю два. Продекодированную информацию снимают с выходов 28 устройства во врем прихода следующего стартового импуль са. В этот момент замыкаются ключи блока 10 и содержимое регистра 3 в параллельном виде проходит на выходы 28 устройства. Если при переборе всех последовательностей формируемых генератором 1 вспомогательных последовательностей на выходе элемента ИЛИ 19 не появляется сигнал логической 1, т.е. веса последовательностей первого и вто рого синдрома оказались больше трех, веса последовательностей первого и второго преобразованных синдромов больше двух, веса всех проверочных последовательностей - больше двух и веса всех преобразованных проверочных последовательностей больше едини цы, то в момент прихода следующего стартового импульса с выходов 28 устройства снимают информацию, записанную в регистре 3 во время предыду 28 щего цикла декодирования а с выхода 29 - сигнал окончания декодирования, который в этом случае равен нулю. Это свидетапьствует о том, что произошла неисправимая ошибка и устройство не смогло продекодировать принятое слово. Процедуру исправления пакета из четырех ошибок по предлагаемому способу рассмотрим на примере. Без oi- раничения общности предположим, что предлагается нулевое кодовое слово и ошибки происходят в первых четырех позициях, т,е. принятое слово записывается в виде у(1П 100 000 000 000 000 000 000), I Введем обозначения у, - первая половина принятого словаJ у - вторая половина принятого слова; S) - послеловательность первого синдрома; S - последовательность второго синдрома; S, - последовательность преобразованного первого синдрома; S ,j - последовательность преобразованного второго синдрома. Последовательности синдромой S, и 5,2 получают в течение первого такта декодирования на выходах блока 6 сумматоров по модулю два в результате выполнения операций, которые могут быть записаны формулами S,y,+y, М; 32 У2+У| М. Для нашего случая слова с четырься ошибками последовательности синдромов S, и Sj равны S((111 100 000 000), 82 (001 111 010 111), а последовательности преобразованных первого и второго синдромов S, сформованных на выходах блока 20 элементов ИЛИ, равны (1 100), 37 (1П1). Вес Хзмминга последовательности преобразованного первого синдрома S , равен двум, т.е. он равен порогу порогового злемента 15. Следовательно, на выходе элемента ИЛИ 19 во время первой половины первого такта декодирования появляется сигнал логической 1, переводящий триггер 23 в единичное состояние. Производится запись в регистр 3 последе9вательности восстаиовленньгх ннформа- ционяых символов Z(, сформированных на выходах кодирующего блока 4. Последовательность восстановленных информационных символов Z формируется в данном случае путем умножения второй половины принятого слова у на матрицу М Z,y М(000 000 000 000). Таким образом, пакет из четырех ошибок исправлен, сигнал на выходе триггера 23, равный логической 1, запрещает прохождение меандра такто вой частоты через элемент ИЛИ 18 и декодирование заканчивается, Рассмотрим пример исправления ошибки кратности шесть. Пусть при передаче нулевого кодо вого слова происходят ошибки на пер вой - третьей и на шестнадцатой восемнадцатой позициях, т.е. у(111 000 000 000 000 111 000 000) . Тогда последовательности S,, 3„, вр пр S , , S J равны S, (100 111 ПО 101) ; Sz (111 100 101 110) ; s7 (1111) .(11 11). веса последовательностей S, и S больше порога порогового элемента 13, веса последовательностей Sj и S больше порога порогового элемен та 1.5, поэтому декодирование продол жается., Генератор 17 вспомогательных пос ледовательностей вырабатывает ненул 2 10 вые вспомогательные последовательности, так как его счетчик 31 (фиг. 4) формирует последовательно адреса с первого по двадцать восьмой по фронту приходящего на его счетный вход меандра тактовой частоты. Таким образом, на втором - двадцать девятом такте декодирования на выходах генератора 17 вспомогательных последовательностей формируются последовательности, соответствующие первому - двадцать восьмому адресам блока постоянной , Для каждой нулевой вспомогательной последовательности, где i 2-9 - номер такта декодирования, на выходах блока 6 сумматоров по модулю два формируются проверочные последовательности j f и , а на выходах блока 20 элементов ИЛИ формируются преобразованные проверочные последовательнопр л сти р,; И .причем последовательности /5,; ( 5, + у-, М) и fif формируются в течение первой половины такта декодирования, а последовательМ) и /5:j ности ( 32 + 1 в течение второй половины такта. Далее производится сравнение весов последовательностей Р,,- и .jj с порогом порогового элемента 14, равного двум, и весов последовательп пр ,, Пр ностеи р/; и р,,; с порогом порогового элемента 16, равного единице. Последовательности Ji, /,; , 5: i; Р 21 формируемые на i-м такте декодирования (),приведены в табл. 2. Таблица2

Изобретение относится к вычислительной технике и технике связи. Его использование в цифровых системах передачи информации позволяет повысить дострверность ее передачи или хранения. Устройство содержит регистр 1, ключи 11 и 12, пороговые элементы 13-15 и злементы ИЛИ 18 и 19. Благодаря введению регистров 2 и 3, кодирующего блока 4, блоков 5 и 6 сумматоров по модулю два, блоков 7-10 ключей, порогового элемента 16, блока 20 элементов ИЛИ и триггеров 2123 обеспечивается возможность распознавания неисправимых ошибок. 1 з.п. ф-Лы, 2 табл., 4 ил. (Л

000 001 110 0100111

110 000 101 0011010

101 101 001 0001110

010 oil 001 100nil

01 1 010 100 001nil

10 on 101 0101111

МО 1 11 010 oil1 1 II

001 000 010 1111011 Таким образом, на двадцать шестом такте декодирования вес последовательности .jg равен единице, т.е. равен порогу порогового элемента 16, Далее с выходов блока 5 сумматоров по модулю два снимается последовательность продекодированных информационных символов Z| , которая форми руется поразрядным сложением по модулю два первой половины принятого слова у и вспомогательной последовательности Jf-je , + }26« Z,(ll 000 000 000)®(1И 000 000 000)(000 000 000 000) Последовательность Z, соответству ет переданному нулевому слову. Ошибка кратности шесть исправлена, и декодирование закончено. Устройство позволяет обнаружить неисправные комбинации из четырех и более опгабок. Например, для кодового слова с ошибками в пятнадцатом, восемнадцатом, двадцать первом и двадцать четвертом символах, проведя указанные операции, получаем, что условия для весов синдромов проверочных последовательностей преобразованных синдромов и преобразованных проверочных последовательностей не выполняются ни для одной вспомогательной последовательности У; , следовательно, произошла неисправимая ошибка, При этом сигнал окончания декодирования после двадцати девяти тактов декодирования равен логическому О, что свидетельствует о том, что прои1512

зошла неисправимая ошибка и что декодирование произведено не бьшо.

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

7216

первого блока сумматоров по модулю два, выходы которого соединены с первыми инфopмaциoнны п входами третьего блока ключей и входами кодирующего блока, выходы которого подключены к вторым информационным входам третьего блока ключей и вторым входам второго блока сумматоров по модулю два, выходы которого соединены с входами первого и второго пороговых элементов и блока элементов ИЛР, выходы которого подключены к входам третьего и четвертого пороговых элементов, выходы которых соединены соответственно с первым и вторым входами второго ключа, выходы первогоои второго пороговых элементов подключены к соответствующим входам первого ключа, управляющие входы ключей объединены и подключены к выходу второго триггера, вход установки в единицу которого соединен с выходом первого триггера, выходы ключей соединены с входами второго элемента ИЛИ, выход которого подключен к входу разрешения считывания третьего регистра и входу установки в единицу третьего триггера, выход которого соединен с вторым входом первого элемента ИЛИ и является выходом сигнала окончания декодирования устройства, выходы третьего блока ключей соединены с информационными входами третьего регистра, выходы которого подключены к информационным входам четвертого блока ключей, выходы которого являются информационными выходами устройства,

2. Устройство по п. 1, о т л и чающееся тем, что кодирующий блок содержит п/2 сумматоров по мо-. дулю два, выходы которых являются выходами кодирующего блока, а входы подключены к входам кодирующего блока в соответствии со столбцами матрицы М, , где G - порождающая матрица входного кода; I - единичная матрица размером п/2 х п/2 - число разрядов входного кода.