Устройство для декодирования двоичного линейного кода

(511 4 Н 03 М 13/О ОПИСАНИЕ ИЗОБРЕТЕНИЯН А ВТОРСНОМ,Ф СВИДЕТЕЛЬСТВУ Зиновьеаков п 3 пГогша Р 5, р. 7 нчиков Е. Т.их кодов, М, 3,7,ОСУДАРСТВЕННЫЙ КОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫ(56) 3 ЕЕЕ Тгапзас 1 опзоп ТЬеогу, 1933, т. 29,750,Колесник В. Д МироДекодирование циклическСвязь, 1968, с. 85, рис 54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНВОИЧНОГО ЛИНЕЙНОГО КОДА(57) Изобретение относится к вычислительной технике и технике связи. Егоиспользование в цифровых системахпередачи информации позволяет повысить дострверность ее передачи илихранения, Устройство содержит регистр1, ключи 11 и 12, пороговые элементы13-15 и элементы ИЛИ 18 и 19, Благодаря введению регистров 2 и 3, кодирующего блока 4, блоков 5 и б сумматоров по модулю два, блоков 7-10ключей, порогового элемента 16, блока 20 элементов ИЛИ и триггеров 2 -23 обеспечивается возможность распознавания неисправимых ошибок.1 з,п, ф-Лы, 2 табл 4 ил.ректор М. Максимишинец Тираж 816 Подписноедарственного комитета СССР 130 Производственно-полиграфическое предприятие, г, Ужгород, ул, Проектн аказ 6046/ ВИПИ Госу по дела 5, Моск изобреа, Жний и открытийРаушская наб д, 4Изобретение относится к высилительной технике и технике передачи данных и может быть использовано в цифровых системах передачи информа - ции,Пель изобретения - повышение достоверности передачи или хранения информации.На фиг, 1 представлена функциональная схема устройства; на фиг, 2схема кодирующего блока на фиг. 3схема генератора вспомогательныхпоследовательностей,Устройство для декодирования двоичного линейного кода содержит первый 1, второй 2 и третий 3 регистры,кодирующий блок 4, первый 5 и второй6 блоки сумматоров по модулю два,блоки 7-10 ключей с первого по четвертый, первый 11 и второй 12 ключи,пороговые элементы 13-16 с первогопо четвертый, генератор 17 вспомогательных последовательностей, первый8 и второй 19 элементы ИЛИ, блок 20элемснтоь ИЛИ, первый 21 второй 22и третий 23 триггеры, Информационныевходы первого 1 и второго 2 реги ","ров являются соответствующими инфор.мационными входами 24 и 25 устройств,выходы разрешения записи регистрови 2, управляющий вход четвертогоблока 10 ключей, вход установки в исходное состояние генератора 1 и входы установки в ноль триггеров 2123 объединены и подключены к входу26 стартового сигнала, Выход 1 первого регистра 1 соединены с первыми информационными входами первого 7 ивторого 8 блоков ключей, выходы второго регистра 2 - с вторыми информационными входами этих же блоков7 и 8, Управляющие входы блоков 79 объединены со счетными входами генератора 17 и первого триггера 21и подключены к выходу первогэ элемента ИЛИ 18, первый вход которого является тактовым входом 27 устройства, Выходы первого и второго блоков 7 и 8 ключей соединены с первыми входами соответствующих блоков 5 и 6 сумматоров по модулю два, Вторые входы первого блока 5 сумматоров подключены к выходам генератора 17, выходы блока 5 соединены с пер:выми инФормационными входами третьего блока 9 кпючей и входамй кодирующего блока 4, выходы которого подключены к вторым входам второго блока 6 сум маторов и вторым информационным входам третьего блока 9 ключей. Выходыэтого блока 9 соединены с информаци -онными входами третьего регистра 3,выходы которого подключены к информационным входам четвертого блока 10ключей, выходы которого являются информационными выходами 28 устройства, Выходы второго блока б сумматоров соединены с входами первого ивторого пороговых элементов 13 ии входами блока 20 элементов ИЛИ,выходы которого соединены с входамитретьего и четвертого пороговых элементов 15 и 16, Выходы пороговых элементов 13-16 подключены соответствен 20 25 30 35 40 45 50 55 но к первому и второму входам первогои первому и второму входам второгоключей 11 и 12, выходы которых соединены с входами второго элемента ИЛИ19, выход которого подключен к входуразрешения считывания третьего регистра 2 и входу установки в единицутретьего триггера 23, выход которогосоединен с вторым входом первогоэлемента ИЛИ 18 и является выходом29 сигнала окончания декодированияустройства, Выход первого триггера21 подключен к входу установки в"1" второго триггера 22, выход которого соединен с управляюшими входамиключей 11 и 12.Устройство предназначено для декодирования двоичного линейного кода(24,12) (расширенный код Голея). Напервый регистр 1 подаются информационные символы, на второй - проверочные, Разрядность всех шин (фиг, 1),кроме выходной шины блока 20 равна12, для шины блока 20 - 4,Пороговый элемент 13 имеетпорог три,элементы 14 и 15 - порог два,элемент 16 -порог один . Блок 20 содержит четыре элемента ИЛИ на три входа каждый.Кодирующий блок 4 выполнен (Фиг,3) на 12 сумматорах 30 по модулю два,выходы которого являются выходамиблока 4, а входы подключены к входамблока 4 в соответствии со столбцамиматрицы М, входящей в выражение дляпорождающей матрицы С, которая длякода (24,12) имеет видс = Д 1,где Э, - единичная двоичная матрицаразмера 12 х 12;И - двоичная квадратная матрицаразмера 12 х 12, имеющая, например, вид4Продолжение табл.1Ъ 1269272 001 000 000 000 000 100 000 000 000 ОО 000 000 000 001 000 000 000 000 100 000 5 5,8 10 203 12 Для кода (24,12) выполняется сле- д 5 13 дующее свойство: если Е, =Е И, тоЕ=Е М, где Е,Е - двенадцатираз рядные двоичные последовательности.Например, входы первого из сумма торов 30 (фиг. 3) соединены с первым, четвертым, пятым, девятым, десятым, 16 одиннадцатым и двенадцатым входамиблока 4, 17Генератор 17 вспомогательных последовательностей содержит счетчик31 и блок 32 постоянной памяти, выхо ды которого являются выходами генера тора 17, а адресные входы соединеныс выходами счетчика 31, вход установ ки в "01 и счетный вход которого являются соответственно входом установ-.4021 ки в исходное состояние и счетнымвходом генератора 17, В блоке 32 по стоянной памяти записаны двадцатьдевять вспомогательных последователь- . 23 ностей, представленных в табл. 1,4524Таблица 011 000 000 000 18 25 50 26 вательность 27 28 000 000 000 000 100 000 000 000 010 000 000 000 Устройство для декодирования двоичного линейного кода (24,12) работает следующим образом,100 310 001 111 010 111 011 100 001 030 111 103 11 О 100 111 001 311 ОО 100 011 010 001 101 311 003 111 100 110 011 100 010 111 111 101 001 010 113 001 110 100 100 011 111 010 101 111 010 001 Вспомогательная последо 000 000 010 000 000 000 001 000 000 000 000 100 000 000 000 010 000 000 000 001 1.0 000 000 000 101 000 000 000 000 110 000 000 000 101 000 000 000 011 000 000 000 000 110 000 000 000 301 000 000 000 011 000 000 000 000 110 000 000 000 101 000 000 000 031 111 000 000 000 000 111 000 000 000 000 111 000 000 000 000 13112 б 92По приходу стартового импульса на вход 26 в регистры 1 и 2 в направляемом виде записывается соответственно информационные и проверочные символы принятого кодового слова, Кроме того, осуществляются выдачи содержащихся в регистре 3 информационных символов предыдущего продекодированного слова через блок 10 ключей на выходы 28 устройства, а также про О изводится установка в исходное состояние генератора 17 вспомогательных последовательностей (причем в исходном состоянии на выходах генератора 17 вспомогательных последовательнос гей ошибок получается нулевая комбинация), и установка в ноль триггеров 21-23, благодаря чему ключи 11 и 12 устанавливаются в верхнее (фиг.и 2) положение, 20На тактовый вход 27 поступает меандр с тактовой частотой, причем фронт первого такта декодирования совпадает с фронтом стартового импульса, а длительность стартового 25 импульса не превышает чувствительности полупериода меандра тактовой частоты. Этот меандр через элемент ИЛИ 18 проходит на управляющие входы блоков 7 - 9 ключей, а также на счетный 30 вход триггера 21,В течение первой половины первоготакта декодирования сигнал на выходеэлемента ИЛИ 18 равен логической "1"(положительный полупериод меандратактовой частоты), Гри этом черезблок 7 ключей символы с выходов регистра 2 поступают на входы блока 5сумматоров по модулю два, а черезблок 8 ключей символы с регистра 1поступают на входы блока 6 сумматоров по модулю два. С выходов блока5 символы поступают на вход кодирующего блока 4, который формирует насвоих выходах символы, соответствующие умножению его входной последовательности на матрицу М, Символы с выходов кодирующего блока 4 в течениепервой половины первого такта декодирования проходят через блок 9 ключейна информационные входы регистра 3,а также на входы блока 6 сумматоровпо модулю два, причем на выходахблока 6 получаются символы последовательности первого синдрома, которыепоступают на входы пороговых элементов 13 и 14, и на входы блока 20элементов ИЛИ,72 ЬНа выходах блока 20 элементов ИЛИполучаются символы последовательностипреобразованного первого синдрома,которые поступают на входы пороговыхэлементов 15 и 6,Пороговые элементы 13 - 1 б построены таким образом, что на выходеэлемента появляетсч сигнал логического 0", если количество единиц средисимволов на входах этого элементапревышает порог, и символ логической"1", если количество единиц на входахне превышает этого порога,Сигналы с выходов пороговых элементов 13 и 15 проходят на входы элемента ИЛИ 19 через ключи 11 и 12,причем при появлении на выходе элемента ИЛИ 9 логической единицы производится запись в регистр 3 символов с выходов кодирующего блока 4,а также устанавливается в единичноесостояние триггер 23, с выхода которого снимают сигнал окончания декодирования, который приходит на.выход29 устройства и на второй вход элемента ИЛИ 18, в результате чего прекращается прохождение меандра тактовой частоты через элемент ИЛИ 18 идекодирование заканчивается,В течение второй половины первого такта декодирования, если декодирование не закончено, сигнал навыходе элемента ИЛИ 18 равен логическому "0" (отрицательный полупериод меандра тактовой частоты),При этом через олок 7 ключей навходы блока 5 сумматоров по модулюдва поступают символы с выходов.регистра 1, а через блок 8 ключей навходы блока 6 сумматоров по модулюдва поступают символы с выходоврегистра 2, в резупьтате чего навыходах блока. б получаются символыпоследовательности второго синдрома,а на выходах блока 20 элементов ИЛИполучаются символы последовательности преобразованного второго синдрома, Символы продекодированной информации поступают на входы регистра 3 через блок 9 ключей с выходов блока 5 сумматоров по модулю два,В начале второго такта декодирования триггеры 21 и 22 устанавливаются в единичное состояние причем на выходе триггера 22 появляется сигнал логической "1, сохраняющийся до прихода следующего стартового импульса, и этот сигнал переводит(фиг, 1 и 2) положение, На входыэлемента ИЛИ 19 поступают сигналы свыходов пороговых элементов 14 и 16,С выходов генератора 17 вспомогательных последовательностей на второми последующих тактах декодированияснимаются ненулевые вспомогательныепоследовательности, при этом в течение первой половины такта декодиро- Ования на входы блока 5 сумматоров помодулю два через блок 7 ключей приходят символы с выходов регистров 2,на входы блока 6 сумматоров по модулю два через блок 8 ключей приходят 5символы с регистра 1, с выходов блока 6 сумматоров по модулю два снимаются символы проверочной последовательности, с выходов блока 20 элементов ИЛИ снимаются символы преобразованной проверочной последовательности, на входы регистра 3 черезблок 9 ключей приходят символы с выходов кодирующего блока 4,В течение второй половины каждого 25такта декодирования на входы блока 5сумматоров по модулю два через блок7 ключей поступают символы с выходоврегистра 1, на выходы блока 6 сумматоров по модулю два через блок 8 ключей приходят символы с выходов регистра 2, на входы регистра 3 через блок9 ключей поступают символы с выходовблока 5 сумматоров по модулю два,Продекодированную информацию снимают с выходов 28 устройства во времяприхода следующего стартового импульса. В этот момент замыкаются ключиблока 10 и содержимое регистра 3 впараллельном виде проходит на выходы28 устройства,Если при переборе всех последовательностей формируемых генератором 17вспомогательных последовательностейна выходе элемента ИЛИ 19 не появля 45ется сигнал логической 1, т,е, веса последовательностей первого и второго синдрома оказались больше трех,веса последовательностей первого ивторого преобразованных синдромов -больше двух, веса всех проверочныхпоследовательностей - больше двух ивеса всех преобразованных проверочных последовательностей больше единицы, то в момент прихода следующегостартового импульса с выходов 28устройства снимают информацию, записанную в регистре 3 во время предыдущего цикла декодирования а с выхода 29 - сигнал окончания декодирования, который в этом случае равен нулю, Это свидетельствует о том, что произошла неисправимая ошибка и устройство не смогло продекодировать принятое слово,Процедуру исправления пакета иэ четырех ошибок по предлагаемому способу рассмотрим на примере. Без ограничения общности предположим, что предлагается нулевое кодовое слово и ошибки происходят в первых четырех позициях, т,е, принятое слово записывается в виде у=(11 100 000 000 000 000 000 000).1Введем обозначенияу - первая половина принятогослова;у - вторая половина принятогогсло ва;Б, - последовательность первогосиндрома;Б - по следо вательно сть второ госиндрома;пРБ, - последовательность преобразованного первого синдрома;Б- последовательность преобразованного второго синдрома,Последовательности синдромовБ, и Бг получают в течение первоготакта декодирования на выходах блока 6 сумматоров по модулю два в результате выполнения операций, которые могут быть записаны формуламиУ УгЛля нашего случая слова с четырься ошибками последовательности синдромов Б и Бг равныБ =( 100 000 000),Бг=(001 111 010 111),а последовательности преобразованныхРпервого и второго синдромов Б иБ г , сформованных на выходах блокар20 элементов ИЛИ, равныБ, = (1100),Б"Р = (1111).гВес Хэмминга последовательностипреобразованного первого синдромаБ, равен двум, т,е. он равен порогу порогового элемента 15, Следовательно, на выходе элемента ИЛИ 19во время первой половины "первоготакта декодирования появляется сигнал логической "1, переводящий триггер 23 в единичное состояние, Производится запись в регистр 3 последоо Номер такта пр 100 000 000 000 000 001 110 010 0111011 010 300 001 1311 010 000 000 000 110 000 303 001 1010303 011 101 030 111 001 000 ООО 000 101 01 003 000 11101 О 111 010 011 3331 000 100 000 000 010 011 001 00 1111001 000 030 131 1013 9 32692вательности восстановленных информационных символов 2 , сформированныхна выходах кодирующего блока 4, Последовательность восстановленных информационных символов 2 формируетсяв данном случае путем умножения второй половины принятого слова у наматрицу М2,=у, м=(ооо ооо ооо ооо),Таким образом, пакет из четырех Оошибок исправлен, сигнал на выходеи итриггера 23, равный логическои 1запрещает прохождение меандра тактовой частоты через элемент ИЛИ 18 идекодирование заканчивается, 15Гассмотрим пример исправленияошибки кратности шесть,Пусть при передаче нулевого кодового слова происходят ошибки на первой - третьей и на шестнадцатой восемнадцатой позициях, т,е,у=-(11 ООО ООО ООО ОООООО000).Тогда последовательности Я , Б,прЯ Б равны 25Я( = (100 111 110 101);Бл = (111 100 101 110);Я", = (1111)Б"Р = (1111).Веса последовательностей Ь, и Б Зрбольше порога порогового элементаПр13 веса последовательностей д иБбольше порога порогового элемен 2та 15, поэтому декодирование продолжается,35Генератор 17 вспомогательных последовательностей вырабатывает ненуле вые вспомогательные последовательности, так как его счетчик 31 (фиг4)формирует последовательно адреса спервого по двадцать восьмой по фронту приходящего на его счетный входмеандра тактовой частоты,Таким образом, на втором - двадцать девятом такте декодирования навыходах генератора 17 вспомогательных последовательностей формируютсяпоследовательности, соответствующиепервому - двадцать восьмому адресамблока постоянной памяти.Для каждой нулевой вспомогательнойпоследовательности, где= 2-9 - номер такта декодирования, на выходахблока 6 сумматоров по модулю два формируются проверочные последовательности ,11, и (3 а на выходах блока 20элементов ИЛИ формируются преобразованные проверочные последовательнопр прсти В и 33, причем последовательности (1(3 =Б,+ М) и (1 фор -мируются в течение первой половинытакта декодирования, а последовательНосТИ 17 2 ( , 82М) и 1 21в течение второй половины такта,Далее производится сравнение весов последовательностей 3, и,с порогом порогового элемента 14,равного двум, и весов последовательпрностей 1, ис порогом порогового элемента 16, равного единице.Последовательности ;, ,;формируемые на 1-м тактепр прдекодирования (1=2-29),.приведены втабл. 2,Таблица 212 1269272 Продолжение табл.2 пр Номер такта пп ооо оо ооо ооо о о оо о000 10 00 О О 000 001 000 000 110 110 О 1 010 1111101 101 000 001 1101 000 000 100 000 101 000 010 011 1011110 011 101 000 110 000 000 010 000 111 011 100 010 111100 00000 10 000 000 001 000 0111010 111 111 1111 000 001 100 100 0111 11 000 000 000 100 011 110 000 001 1101 000 101 011 010 О 11 12 000 000 000 001 000 100 001 11 0111 011 111 010 100 111130 1001 26 000 111 000 000 О 00 Таким образом, на двадцать шестом такте декодирования вес последоваПДтельностиг гб равен единице, т,е. равен порогу порогового элемента 16.45Далее с выходов блока 5 сумматоров по модулю два снимается последовательность продекодированных информационных символов Е которая формируется поразрядным сложением по мо 50 дулю два первой половины принятого слова у и вспомогательной последовательности: 2=У+33 гьЕ, =(11 000 000 000)111 ООО 000 000)=(000 000 000 000)фПоследовательность Е, соответствует переданному нулевому слову, Ошибка кратности шесть исправлена, и декодирование закончено,Устройство позволяет обнаружить неисправные комбинации из четырех и более ошибок, Например, для кодового слова с ошибками в пятнадцатом, восемнадцатом, двадцать первом и двадцать четвертом символах, проведя указанные операции, получаем, что условия для весов синдромов проверочных последовательностей преобразованных синдромов и преобразованных проверочных последовательностей не выполня.ются ни для одной вспомогательной последовательностиследовательно, произошла неисправимая ошибка,При этом сигнал окончания декодирования после двадцати девяти тактов декодирования равен логическому 0, что свидетельствует о том, что прои зошла неисправимая ошибка и что декодирование произведено не было. 1269272первого блока сумматоров по модулю два, выходы которого соединены с пер Формула изобретения 1, Устройство для декодирования двоичного линейного кода, содержащее первый регистр, первый, второй и третий пороговые элементы, первый и второй ключи, первый и второй элементы 1 О ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью повышения достоверности передачи или хранения информации, в него введены второй и третий регистЭры, блоки ключей с первого по четвер тый, первый и второй блоки сумматоров по модулю два, кодирующий блок, четвертый пороговый элемент, первый, второй и третий триггеры, блок элементов ИЛИ и генератор вспомогатель ных последовательностей, вход установки в исходное состояние которого объединен с входами установки в "О" всех триггеров, управляющим входом четвертого блока ключей и входами 25 разрешения записи первого и второго регистров и подключен к входу стартового сигнала устройства, информационные входы первого и второго регистров являются соответствующими 30 информационными входами устройства, выходы первого и второго регистров соединены соответственно с первыми и вторыми информационными входами первого и второго блоков ключей, управляющие входы которых объединены с управляющим входом третьего блока ключей, счетными входами генератора вспомогательных последовательностей и первого триггера и подключены к выходу первого элемента ИЛИ, первый вход которого является тактовым входом устройства, выходы первого и второго ключей соединены с первымивходами соответствующих блоков сумма. торов по модулю два, выходы генератора вспомогательных последовательностей подключены к вторым входам выми информационными входами третьего блока ключей и входами кодирующего блока, выходы которого подключенык вторым информационным входам третьего блока ключей и вторым входам второго блока сумматоров по модулюдва, выходы которого соединены с входами первого и второго пороговых элементов и блока элементов ИЛИ, выходы которого подключены к входам третьего и четвертого пороговых элементов, выходы которых соединены соответственно с первым и вторым входами второго ключа, выходы первогои второго пороговых элементов подключены к соответствующим входам первого ключа, управляющие входы ключейобъединены и подключены к выходу второго триггера, вход установки в единицу которого соединен с выходом первого триггера, выходы ключей соединены с входами второго элемента ИЛИ,выход которого подключен к входу разрешения считывания третьего регистра и входу установки в единицу третьеготриггера, выход которого соединен свторым входом первого элемента ИЛИи является выходом сигнала окончаниядекодирования устройства, выходы третьего блока ключей соединены с информационными входами третьего регистра,выходы которого подключены к информационным входам четвертого блока ключей, выходы которого являются информационными выкодами устройства,2, Устройство по п, 1, о т л и ч а ю ш е е с я тем, что кодирующий блок содержит и/2 сумматоров по модулю два, выходы которых являются выходами кодирующего блока, а входы подключены к входам кодирующего бло" ка в соответствии со столбцами матрицы М, С= 1/М, где С - порождающая матрица входного кода; 1 - единичная матрица размером и/2 х и/2 - числоразрядов входного кода