Устройство для исправления ошибок кодов боуза-чоудхури- хоквингема

 

Изобретение относится к автоматике и вычислительной технике и может использоваться для повышения достоверности обработки и передачи дискретной информации. Цель изобретения - повышение помехоустойчивости устройства. Устройство для исправления ошибок кодов Боуза-Чоудхури-Хоквинима содержит датчики 1,2 и 23 импульсов, сумматора 3,5,8,19 и 37, блоки 4,10 и 12 вычитания, блоки 6 и 16 умножения, блок 7 логарифмирования, блоки 8,11 и 22 деления, блоки 20 и 24 сравнения, элементы И 18,21,27,31,39,33 и 36, регистры 35,13,17, регистры 25 и 38 сдвига, входной и выходной регистры 32 и 40, элементы ИЛИ 29 и 34, триггеры 26 и 30, реверсивный счетчик 28, регистр 14 адреса и блок 15 постоянной памяти. 2 ил.

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

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

РЕСПУБЛИК

„„80„„1531227

А1 (51)4 Н 03 М 13/0

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ. ГОСУДАРСТВЕННЫЙ НОМИТЕТ

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

ПРИ ГКНТ СССР (21) 4281067/24-24 (22) 09.07.87 (46) 23.12,89. Вюл. № 47 (71) Винницкий политехнический институт (72) А.А. Клемешов ) И.11.Мусаев, Л.А.Шарейко и С.В.10химчук (53) 681. 3 (088. 8) (56) Авторское свидетельство СССР № 1115055, кл. G 06 F 11/10, 1982.

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

¹ 1185611, кл. Н 03 М 13/00, 1983. (54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОШИБОК КОДОВ ВОУЗА-ЧОУДХУРИ-ХОКВИНГЕ11А (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для повышения досто2 верности обработки и передачи дискретнои информации. Цель изобретения— повышение помехоустойчивости устройства. Устройство для исправления ошибок кодов Воуза-Чоудхури-Хоквинима содержит датчики 1,2 и 23 импульсов, сумматора 3,5,8,19 и 37, блоки 4,10 и 12 вычитания, блоки 6 и 16 умножения, блок 7 логарифмирования, блоки

8,11 и 22 деления, блоки 20 и 24 сравнения, элементы И 18, 21, 27,31, 39, 33 и 36, регистры 35, 13,17, регистры 25 и 38 сдвига, входной и выходной регистры 32 и 40, элементы

ИЛИ 29 и 34, триггеры 26 и 30, реверсивный счетчик 28, регистр 14 адреса и блок 15 постоянной памяти. 2 ил .

1531227

Изобретение относи» < я к л нтом,» ги-ке и нычисггительной технике и может зом

11ернонячяльно н с ум> гор 5 заносит— с>» !»I>o»»чное число, соотнетс»нующее

35 единице, н б:Ioh . »»»тл»3»я зс»»»оситсл двоичное число, .оо. тстнующее коли»e<"rBv информл»»ионных символо 3 кодовой комбин.>ци»>,: осту»»ям<ней нл перный информ,<пис ннь;и нхоп устройс гна, в блок 6 умножения з Ill< с.ится дно.>нное

40 число, соо» ве r<"гнук>щее двойке, н реги<.тр 1 3 »a»»<>< I» r< >! дноично».

> ООГH» T TBÓ». I>IÅÅ ЕЛИНИЦЕ, НЛ ВХОД сумматора 9 !!<><"ry»lac г дном II»<>å число, соотнетстнуюше единице. В блоке 15 пост Зя>»>»о I naw>» ri» злпислны значения минин».I>l I»I х цолиномон с < nО» ветствую»ш»ми адресами.

К<1»»онл»» кс>мбиняция, злкодиронлннля циклическиМ ко,»ом (Е, К), по<: r yr»a50 е г на вход р» ãii< гра 32 и од»»овременно на перные нходы счетчиков 1 и 2 (счетчик считает ксличес:твс единиц, л счетчик 2 — количество н лей кодовой комб»»н<3»ц»>,) . Ня перный вход сумматора 3 I!<>!Is». > ся .»н<>ичное число, с.ос>тне гс"» нук>ще<= количеству»» ..»ей принимаемой к д н< и . омбиняции, я нтоиспользонлться для понышения достоверности обряботки и Il< редлчи дис5 кре rH»>H информации.

11ельк> изобретения янляется повышение помехоустойчивости устройства.

На фиг. 1 r!pens тянленл функциональная схема y<"rpo!»< твя; на фиг, 2временная диаграмма сиги :»oH нл входах устройстня.

Устройство с одер>»<»»т с.четчики 1 н

2 имг»ульсон, < умматор 3, блок 4 вычитания, с:уммягор 5, б;><:к 6 умножения, :лок 7 логарифмирования, блок 8 деления, суммятор 9, блок 10 вычитания, блок 11 деления, блок 12 вычитания, регистр 13, регис гр 14 адреса, блок

15 постоянной памяти, блок 16 умноже- 20 ния, реги< тр 17, элеме»» r И 18, с:умма»ор 19, блок 20 сря!II»el»», элемент

И 21, блок 22 деления, < >leò>;»ê 23 импульсов, блок 24 оряннения, регистр

25 сднигя, триггер 26, элемент И 27, 25

per3ep<.I»I3I»I,III » че гчик 28, э !e»»e!» r ИЛИ

29, триггel> 30> .3>»еw» II г И 31, входной рег,»< тр 32, эд< м<.н г И 33. Э»»е;>он г Ш1И 34, ppi ист» 35, шлеме»»T И 36, ;ммлтор 3 l, реги<; р»<> сдвиг л, элеME :!i r И 39, »3!>»h>)(II» <>1» » t Гис Тр 4 0 .

Устройстно рябо слет < ле»>ую>»>»»м обрярой вход сумматора 3 подается двоичное число, соответствующее количеству единиц принимаемой кодовой комби-, нации. С выхода сумматора 3 количество символов, соответствующее результату суммирования, подается одновременно на вход сумматора 5 и вход блока 4 вычитания. С выхода блока 4 двоичное число, соответствующее количеству проверочных символов, подается на первый вход блока 6. Одновременно на второй его вход подается сигнал, соответствующий двойке.

С выхода блока 6 двоичное число, соо<ветствующее результату умножения, подается на первый вход блока 8 деления. С выхода сумматора 5 результат суммирования подается на вход блока 7 логарифмирования по основанию два. С выхода блока 7 двоичное число, соответствующее результату логарифмирования, подается одновременно на второй вход блока 8 и на вхо, младших разрядов регистра 13. С выхода блока 8 двоичное число, соответствующее результату деления, подается на первый вход сумматора 9, на второй вход которого подается двоичное число, соответствующее единице.

С выхода сумматора 9 двоичное число, соответствующее результату суммирования, подается одновременно на первый вход блока 12 и первый вход блока 10.

С выхода блока 10 на первый вход блока 11 деления подается двоичное число, <3orâåòñòâóloùåå результату вычитя»»»»я, нл второй его вход подается число два. С. выхода блока 1 на первый вход блока 24 сравнения подается двоичное число, соответствующее результату деления. На второй вход блока 12 подаетс.я двоичное число, соответствующее единице. С выхода блока 12 двоичное число, соответствующее результату вычитания, подается на второй вход блока 20 сравнения.

Одновременно на управляющий вход регистра 13 подается сигнал, который обеспечивает подачу двоичного числа, соответствующего единице, одновремен«о на первый вход сумматора 19 и на нход старших разрядов регистра 14.

С выходя регистра 14 сформированный адре<. прступает на вход блока 15. С выхода блока 15 выбранный минимальный полином подается на первый вход блока 16. Одновременно на второй вход блока 16 с выхода регистра 17 подает15312 ся двоичное число, соответствующее единице, поскольку на вход регистра

17 подается высокий потенциал девятого информационного входа. С выхода

5 сумматора 31 двоичное число, соответствующее результату суммирования, подается одновременно на второй вход элемента И 21 и первый вход блока 20, В блоке 20 сравнивается двоичное чис- 1О ло, соответствующее результату суммирования в сумматоре 19 с двоичным числом, соответствующим порядку старшепо из минимальных полиномов, которое подается с выхода блока 12. Если двоич- 15 ное число, которое подается на первый вход блока 20, меньн!е или равно двоичному числу, соответствующему порядку старшего изминимальных полиномов, то тогда на первом выходе Меньше или 20 равно" блока 20 появится сигнал, который обеспечивает подачу двоичного числа с выхода сумматора 19 через элемент И 21 на информационный вход регистра 13. Это двоичное число с вы- 25 хода регистра 13 подается одновремен«о на вход старших разрядов регистра

14 и на первый вход сумматора 19. С выходов регистра 14 сформированный новый адрес подается на вход блока 30

15. С выхода блока 15 выбранный новый полином подается на первый вход блока

16. В блоке 16 выбранный новый полином умножается на предыдущий. Результат умножения записывается в регистр

17. На второй вход сумматора 19 одно35 временно с десятого информационного входа подается двоичное число, соответствующее единице. Результат суммиОвания подается на BTc)poH Вход зле 40 мента И 21 и первый вход блока 20 °

В блоке 20 сравниваегся двоичное число, соответствующее результату суммирования в сумматоре 19 с двоичным числом, соответствующим порядку старшего из минимальных полиномов, которое подается с выхода блока 12. Если двоичное число, которое подается на первый вход блока 20, меньше или равно двоичному числу, оответствующе- 50 му порядку старшего из минимальных !! полиномов, на первом выходе Меньше или равно" блока 20 появляется сигнал, который обеспечивает подачу двоичнога числа с выхода сумматора 19 че55 рез элемент И 21 íà информационный вход регистра 13. Затем повторяется процедура выбора и умножения полиномов. Эта процедура продолжается до

27 6 тех пор, пока на втором выходе блока

20 "Больше" не появится сигнал. С появлениеМ на втором выходе "Больше" блока 20 сигнала обеспечивается подача двоичного числа, соответствующего результату умножения полиномов, находящихся в регистре 17, через элемент И 18 на второй вход блока 22 и одновременно подача принятой кодовой комбинации, находящейся в регистре 32, через элементы И 33, HJIH 34 на вход регистра 35. С выхода регистра 35 принятая кодовая комбинация подается одновременно на второй вход элемента И 36, информационный вход регистра 25 сдвига, который сдвигает информацию на один разряд влево и первый вход блока 22. В блоке 22 принятая кодовая комбинация делится на соответствующий выбранный образующий полином. С выхода блока

22 остаток от деления подается одновременно на первый вход элемента И

31 и управляющий вход сложения счетчика 23. С выхода счетчика 23 вес остатка от деления подается на второй вход блока 24, на который также подается двоичное число, соответствующее количеству исправляемых ошибок с выхода блока 11. В блоке 24 происходит сравнение количества исправляемых ошибок с весом остатка от деления. В случае, если количество исправляемых ошибок меньше, чем вес остатка от деления, на первом выходе блока 37 !!Меньше появляется сигнал, который подается одновременно на управляющий вход сложения счетчика 28, вход триггера 26 и на разрешающий вход регистра 25 сдвига на один разряд влево.

После сдвига на один разряд влево с выхода регистра 25 кодовая комбинация подается на первый вход элемента И 27. Одновременно с выхода триггера 2Ь разрешающий сигнал подается на второй вход элемента И 27. Этот сигнал обеспечивает подачу сдвинутой кодовой комбинации через элемент

HJIH 29 на вход регистра 25, с выхода которого сдвинутая кодовая комбинация подается одновременно на второй вход элемента И 36, первый вход блока 22 и информационный вход регистра

25. В блоке 22 происходит деление сдвинутой кодовой комбинации на выб« ранный образующий полином. С выхода блока 22 остаток от деления подается одноврем нно на первый вход элемен1531227 та И 31 и управляющий вход сложения счетчика 23. С выхода его вес остатка от деления подается на второй вход блока 24, где происходит сравнение количества исправляемых ошибок с ве5 сам остатка от деления. В случае, если количество исправляемых ошибок меньше, чем вес остатка от деления, на первом выходе блока 24 "Меньше" появляетcF! сигнал, когорый подается одновременно на разрешающий вход сложения счетчика 28, вход триггера 2б и на разрешающий вход регистра 25. Iloсле сдвига на один ра" ðÿä влево с вы!

5 хода регистра 25 вновь сдвинутая кодовая комбинация подается на первый вход элрмента И 27. Одновременно с выхода триггера 26 решающий сигнал обеспечиваег подачу с. выхода элемснra

И 27 вновь сдвинутой кодовой комбина-ции на вход регистра 35 чере элемент

И!1И 34 . Э ra процедура повторяется до тех пор, пока в блоке 24 количества исправляемых ошибок будет больше или равно веса остатка от деления, С второго выхода блока 24 "Больше или равно сигнал подается одновременно на первый вход элемента ИЛИ 29, второй вхап элеь ента И ".I u второй вход элеме та И 3б. 11ри том остаток от деления подается на второй вход сVMматора 37 через эл;". елr И 3!. Одновременна на первый вхо, умматара

37 падаетсв пж ледняя сдвинутая комбинация череэ " «::.э И Эб. С выхода

35 сумматора 37 результ г уммпрования подае гся на информационный вход pe!.!iтра 38, в котором происходит сдвиг информации на сдпн разряд «право.

В это время с выхода эл;:мента И. П 29 на вход счетчика 38 подается у: равляющий сигнал вычита .я, ".аторыи обе печивает вычитание единицы нз падсчитанного числа, соотьет< твующего коли45 .еству сдвигов в. е», С вь хода счетчика 28, сост нет от ву, щего ненулевому со< таянию, сигFl.lë п даетсл одновременно на вход триггера 30 и разрешающий вхсд регистра 33, при этом происходит сдвиг одного разряда впра50 ва. В э го время с выхода триггера 30 через элемент Ш1И 29 на вход счетчика 28 подается управляющий сигнал вычитания. 11о:.ле вторичного вычитания сигнал с выхода счетчика 28 падается одновременна на вход триггера 30 и разрешающий вход регистра 38, при этом происходит вторичный сдвиг идного раэряда вправо. Эта процедура продолжается до тех пор,пока на выходе, соответствующем нулевому состоянию счетчика 28, не появится сигнал.

Этот сигнал обеспечивает подачу с выхода регистра 38 на вход выходного регистра 40 через элемент 39 и исправленной кодовой комбинации. С появлением запрещающего сигнала на первом управляющем входе устройство прекращает прием кодовой комбинации.

Отметим, что цифровая информация, и пользуемая при работе устройства, представляется в двоичной системе, счисления.

Введение блока 15 постоянной памяти, блока 7 логарифмирования по основанию два, блоков 4, 10 и 12 вычитания и блоков 20 и 24 сравнения позволяет осуществить автоматическое получение образующего полинома для различньгх кодовых расстояний кодов

БЧХ. Выбор образующего полинома позволяет осуществЛять исправления ошибок соответ твующей кратности за

ñчет введения регистров 25 и 38 сдвига, реверсивного счетчика 28. ИсправЛение ошибок различной кратности производится путем < равнения веса остатка от деления принимаемой кодовой комбинации на полученный образующий полинам с кратностью исправляемой ошибки, что значительно повышает корректирующую способность предлагае«ого устройства и автоматически приводит к повышению достоверности контроля. Кроме того, устройство можег исправлять, ошибки любой кратности, соответствующей таблице минимальньгх полиномов, хранимой в блоке 15. ф а р и у л а и з о б р е т е н и я

Устройство для исправления ошибок кодов Боуза-Чоудхури-Хоквингема, содержащее входной регистр, вход которого является первым информационным входом устройства, первый элемент И, выход которого ггодключен к входу выходного регистра, выходы которого являются выходами устройства, первый регистр сдвига, тактовый вход которого объединен с входом первого триггера, первый и второй счетчики импульсов, второй триггер, первый и второй элементы ИлИ, первый и второй блоки деления, о т л и ч а ю щ е е с я

1531227

reM, что, с целью повышения памехоус.тойчивости устройсTB

И, блок логарифмирования, блоки сравнения, регистры, сумматоры, третий, блок деления, блоки вычитания и блоки умножения, первые и вторые входы первого и второго с:четчиков импульсан попарно объединены и подключены соответственно к первому информационному и первому управляющему входам ус."тройства, выходы первого и второго с.четчикон импульсов и входного регистра подключены соотвеrcтвенно к первому и второму входам первого сумматора и первому входу второго э:1емента

И, выход которого соединен с первым входом первого элемента ШП1, выход которого соединен с входом первого регистра, выход котараго подключен к первому входу первого блока деления, 25 информационному входу первого регистра сдвига к первому входу тре гьего элемента И, выход которого подключен к первому входу второго сумматора, выход которого соединен с информационным входом второго регис.гра сдвига, выход которого соединен со своим входом обнуления и первым входам первого элемента И, выход первого сумматора подключен к первым входам третьего

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

55 седьмым информа11иа1111ыми входами устройства, выходы втор 11 i> и третьего блоков нычи гания падь.1ю I(ны с:аотнетственно к первым входам первого блока сравнения и третьего блока деления, втораи вход которого является восьмым информационным входом устройства, а выход подключен к первому входу второго блока сравнения, первый вьгход которого соединен с вторым входом третьего элемента И и первыми входами четвертого элемента И и второго элемента ИЛИ, выходы которых подключены соответстненна к второму входу второго сумматора и вычитающему входу реверсинного счетчика, первый выход которого через второй триггер соединен с вторым входом второго элемента ИЗБ и непосредст" ненно подключен к тактовому входу второго регистра сдвига, первый выход первого блока сравнения соединен с вторым входом второго элемента И и первым входом пятого элемента И, выход которого подключен к второму входу первого блока деления, выход которого соединен с вторым входом четвертого элемента И и информационным входам третьего счетчика импульсов, тактаныи вход которого является перBIIM синхронизирующим входом устройства, а выход подключен к второму входу второго блока сравнения, второй выход которого подкл1очен к входу первого триггера и суммирующему входу реверсивного счетчика, тактовый вход каторога является вторым синхронизирующим входом устройства, выход подключен к второму входу первого элемента И, выход первого регистра сдвига подключен к своему входу обнуления и первому входу шестого элемента

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

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

1531227

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

ЮЪ

1 1

ЬR

4р - ъ ) й (ь Ъ

4 )3 и

Составитель О.Тюрина

Техред Л.Олийнык

Корректор И.Муска

Н.Лазаренко

Редактор

Закаэ 7967/57 Тираж 884 ° Подписное

BHHHIIH Государственного комитета по иэобретениям и открытиям при. ГКНТ СССР

1130 35, Москва, Ж-35, Раушская наб., д. 4/5 (1роиэводственно-иэдательский комбинат "Патент", г.ужгород, ул. Гагарина,101