Декодер кодов боуза-чоудхури-хоквингема

СОЮЗ СОВЕТСКИХСОЦИАЛ ИСТИ Ч ЕСКИХРЕСПУБЛИК9) (11) 2(я)5 Н 03 М 13/ АНИЕ ИЗС)БРЕТЕ Н И ОП ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР(ГОСПАТЕНТ СССР) АРТО РС КОМУ С В ИДЕТ ЕЛ Ь СТ(71) Ленинградский механический институтим, Маршала Советского Союза Устинова Д.ф,(56) Авторское свидетельство СССРМ 1457166, кл, Н 03 М 13/02, 1987.Мак-Вильямс Ф,ДжСлоэн Н,Дж,А. Теория кодов, исправляющих ошибки. - М.:Мир, 1979, с. 267-272,(54) ДЕКОДЕР КОДОВ БОУЗА-ЧОУДХУХОКВИН ГЕМА(57) Изобретение относится к вычислительной технике и связй. Его использование в системах передачи дискретной информации позволяет повысить" быстродействие дек:- дера. Декодер содержит блоки 1,2 вычисле - ния элемента синдрома, узел 4 формирования многочлена локаторов оши бок, блок 6 формирования решений и блок 11 коррекции ошибок, Благодаря введению в декодер блок 3 вычисления синдрома, блока 5 деления, блока 7 умножения, блока 8 сложения и дешифраторов 9, 10 время исправления ошибок сокращается. 1 з.п. ф-лы, 3 ил,(1 2 4 6 8 10 12,14, 1 3 5 1 9 11 13)5 Н 2= 10 15Нз= Блоки 1,2 и 3 вычисления элементов20 синдрома выполняют операции; Яз= Нз Х, Я 2= Н 1 Х; Я 2 = Н 2 Х;где Х - входное кодовое слово, и выполняются каждый в виде четырех сумматоров по 25 модулю ва еализ ю их нк и Х 15 Х 14 Х 15 3+ Х 5+ Х 6+ Х 7+ Х 8+ Х 12+ Х 7+ Х 9 + Х 11 + Х 12+ Х 13 + Х 5+ Х 6+ Х 7+ Х 11+ Х 15+ + Х 8+ Х 10 + Х 12 + Х 13 + Х 14 3 3 = Х 1 + Х 5+ Х 6 + Х 10 + Х 11 + Х 15гз:8 3 = Х 4+ Х 5+ Х 9+ Х 10+ Х 14+ Х 15ЯЗ = 3 = ХЗ+ Х 5+ Х 8+ Х 10+ Х 13+ Х 1543 = Х 2+ ХЗ+ Х 4+ Х 5+ Х 7+ Х 8+ Х 9+Х 10 40 +Х 12 + Х 13 + Х 14 + Х 15Блок 14 деления выполняет операциюделения ЯЗ/Я 1 в полях Галуа ОГ(2). Пусть Яз -а, Я 1=сР, гдето, р б(0,114), а Яз, Я 1 - 45 элементы матрицы Н 1, то яз/я 1чар х а = а р. Блок 14 выполняетР +1) аод 15ся, как показано на фиг. 2, Он содержит дешифраторы 16,17, группу из 15 И 5 элемен тов И, 18 и шифратор 19 из четырех элементов ИЛИ. На входах элементов И 18 дешифрируются все сочетания значений Яз И Я 1, а выхОД КажДОгО иэ них СОединЕн с входами элементов ИЛИ шифратора 19 с номерами, равными номерам единичных разрядов в представлении Яз/Я 1.Блок умножения выполняется как псказано на фиг. 3, Он содержит дешифраторы 20,21,25, сумматор по модулю К 24, ыифраторы 22, 23 и 26, Шифраторы 22 и 23 выполН 1- (1,а,аг,а,С,Р,9 10 11 12 13 141 1вида 00010011010 10011 01 0111 01001101011 0 01 0011 0101 0010 Изобретение относится к области вычислительной техники и связи и может использоваться для систем передачидискретной информации,Цель изобретения - повышение быстродействия декодера,На фиг. 1 показана структурная схемадекодера; на фиг. 2 - схема блока деления вполях Галуа; на фиг. 3 - схема блока умножения в полях Галуа.Декодер содержит первый блок 1 вычисления элемента синдрома Яз, второй. блок 2 вычиСления элемента синдрома Я 1,третий блок 3 вычисления элемента синдрома Яг, узел 4 формирования многочлена локаторов ошибок о(Е), блок 5 деления, блок6 формирования решений, блок 7 умножения, блок 8 сложения, дешифраторы 9,10,блок 11 коррекции ошибок, входы 12, выходы 13,Информационные входы 12 устройствасоединены с входами блоков 1,2,3 вычисления элементов синдрома, выходы которыхсоединены с входами узла 4 формированиямногочлена локаторов ошибок, соединенного выходами с входами делимого блока 5деления, входы делителя которого соединены с выходами блока 3 вычисления элемента синдрома Я 2, а выходы - с входами блока6 формирования решения, соединенного 3выходами с первой группой входов блока 7. умножения, вторая группа входов которогосоединена с выходами блока 2 вычисленияэлемента синдрома Я 1, а выходы - с входамидешифратора 10 и блока 8 сложения, соединенного второй группой входов с выходамиблока 2 вычисления элемента синдрома з 1,а выходами - с входами дешифратора 9,выходы которого соединены с второй группой входов блока 11 коррекции ошибок, соединенного первой группой входов с,декодера.Реализацию блоков и функционирование устройства рассмотрим для случае 15 разрядного БЧХ-кода, порождаемого, полиномом а + а+ 1 и имеющего проверочную матрицу 101 01 1 1 10001001 001001101011110 01 01 1 110001 001 1 0001 001 1 01 01 1 1 1 Нз = 1, а 3 а 6 а 9, а 1, аз, а 8,а,а,1,аз,а а а ") 100011000110001 000110001100011 001 010010100101 011110111101111 д,р у щ фу ци,2 = Х 1+ Х 5+ Х 8+ Х 9+ Х 11+ Х 13+ Х 14+ Х 152з =1 = Х 2 + Х 5+ Х 6 + Х 8+ Х 10 + Х 11 + Х 12 + Х 1341 = ХЗ + Х 7 + Х 6 + Х 9 + Х 11 + Х 12 + Х 13 + Х 141 = Х 4+ Х 7 + Х 8+ Х 10 + Х 12 + Х 14 + Х 13+ Х 152= Х 1+Х +32- ХЗ+ Х 65 п 1" В0110 0001 0011 ОООО няются в виде четырех элементов ИЛИ и по единичному сигналу на выходе дешифратора 20 и 21 соответственно, соответствующему входному коду а,а по матрице Н 1 формируют выходной код числа Ц. Сумматор по модулю К; в данном случае К = 15, формирует код числа(1+л 1 об 15 = г, а дешифратор 25 и шифратор 26 формируют кодовую комбинацию, соответствующую а матрицы Н 1.Блок 7 умножения выполняется аналогичн-.1 изображенному на фиг. 3.Блоки сложения 8 и 15 выполняются в виде четырех сумматоров по модулю два, осуществляющих поразрядное суммирование входных кодов,Блок 5 деления выполняется аналогично изображенному на фиг, 2.Блок 6 формирования решения осуществляв; операцию умножения Впп Х, где для полинома а + а + 1 а Х - входной код, равный Х = ( х х х х). В соответствии с этим блок реализуется в виде а= хг+х 1 а =хг оа 1 х 1+ х ао 0 Блок 11 коррекции ошибок выполняется в виде и сумматоров по модулю два.Для других БЧХ-кодов конкретная схемная реализация блоков определяется матрицами Н 1, Н 2, Нз в соответствии с описанным выше порядком.Работа декодера происходит следующим образом,Пусть на входы декодера подана кодовая комбинация, имеющая ошибки в третьем (х ) и в десятом (х 9) разрядах. При этом на выходах блоков 1,2,3 вычисления элементов синдзрома формируются сигналы 3 з = Нз" хХ=(а ) +(а 9) =а +а" =1100+1111 =0011 = а,32= Н 2 Х=(а +(а) =а" + а =0011+ +1000=1011=а 31 = Н 1 Х = а 2+ а 9 = 0100 + 1010 = 1110 По сигналам 3 з, 31 узел 4 формирования многочлена локаторов ошибок формирует сигнала(у): 3 зд 1 + 32 а а 11+ + ат а 11На выходе блока деления вырабатыва. ется сигналО =с(Е) /32= а"/а=а =ОО 11,который поступает на входы блока 6 формирования решения, производящего операцию 0110 00001 00011 1 =1100= аб0000 1игнал с выхода блока 6 поступает на вход блока 7 умножения, при этом на его10 выходе будет кодЕ-т 31=а а - а =аг =0100,являющийся первым корнем, на основе которого дешифратор 10 формирует единичный сигнал на третьем выходе, поступающий"5 на вход третьего сумматора по модулю дваблока 11 коррекции ошибок, на первый входкоторого поступает сигнал третьего разрядавходного кода х, при этом корректируетсяошибка в данном разряде. Кроме того, сигнал с выхода блока умножения 7 поступаена входы блока сложения 8, на выходах которого формируется кодЧ=Е+31=а +( а +а )= а1010.который поступает на входы дешифратора9, на десятом выходе которого при этомформируется единичный сигнал, поступающий на вход десятого сумматора по модулю30два, на первый вход которого поступает сигнал х десятого разряда входного кода, приэтом корректируется ошибка в данном разряде,Таким образом обе ошибки исправлены.Исправление ошибок осуществляется врезультате решения уравнениях + 31 х + (3 1+ - ) = О,г г 3 з31путем замены переменныхх=у 31при этом(д+ 3 з)45 3 1(уг+у+ " )=О,31 Решение уравнения у + у+ О = 0 осуществляется с использованием матрицы Вв 1 л Первый корень уравнения равен(+ 3 з)Х 1=( Ввп( ) 3131 а второйХг = 31+ Х 1.Таким образом в предложенном устройстве декодирование осуществляется комбинационным устройством, что обеспечивает повышение быстродействия,1783627 3 5, Ф о рмул а изобретения 1, Декодер кодов Боуза-Чоудхури-Хоквингема, содержащий первый и второй блоки вычисления элемента синдрома, выходы которых соединены соответственно с первыми и вторыми входами узла формирования многочлена локаторов ошибок, блок формирования решений и блок коррекции ошибок, выходы которого являются выходами декодера, о т л и ч а ю щ и й с я тем, что, с целью повышения быстродействия декодера, в него введены блок деления, блок умножения, блок сложения, первый и второй дешифраторы и третий блок вычисления элемента синдрома, входы которого соответственно объединены с входами первого и второго блоков вычисления элемента синдрома, первыми входами блока коррекции ошибок и являются входами декодера, первые входы блока сложения соответственно объединены с первыми входами блокаумножения и подключены к выходам второго блока вычисления элемента синдрома, выходы третьего блока вычисления элемента синдрома соединены с первыми входами блока деления и третьими входами узла формирования многочлена локаторовошибок, выходы которого подключены к вторым входам 5 блока деления, выходы которого через блокформирования решений соединены с вторыми входами блока умножения, выходы которого подключены к входам второго дешифратора и вторым входам блока сложе ния, выходы которого соединены с входамипервого дешифратора, выходы первого и второго дешифраторов подключены соответственно к вторым и третьим входам блока коррекции ошибок.16 2,Декодерпоп.1,отличающийсятем, что узел формирования многочле а ло.катаров ошибок содержит блок сложения н блок деления, первые и вторые входы которого являются одноименными входами уз.20 ла, выходы блока деления подключены кпервык; входам блока сложения, вторые входы и выходы которого являются соответст.венно третьими входами и выходами узла..5 ктор Л.Лука Редактор Г.Бельск оизводственно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина. 101 аказ 4522 ВНИИПИ Госуд оставитель О,Музыченкехред М,Моргентал Тираж Подписное.венного комитета поизобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб 4/5