Устройство для исправления ошибок при итеративном кодировании

2 Я 253 Союз Советских Социалистических Республикс Зависимое от авт. свидетельстваЗаявлено 28,111.1968 ( 1228748/18-2 Кл. 4 О с присоединением заявки Х МПК С 061 оритет Комитет ло делам изобретений и открыти при Совете Министров СССР,Н 11. юллетень27 ДК 681.326.75(088 публикован бликования описания 4.11.19 Да Авторизобретени Л, Д. Кислю Заявитель УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОШИБ ПРИ ИТЕРАТИВНОМ КОДИРОВАНИИ способом. Если в строке 5 у число ошибок 1 (и, то в результате процедуры исправления будет получена кодовая комбинация рул =5 у, где 5 у, - комбинация, являющаяся 1-ой строкой неискаженного итеративного кода на передаче. Если же число а(1 у (д, то после исправления получим 5 ул - 5 у+ 5 у,т, где 5 у,т - комбинация, в которой символ 1 находится на 1 у местах, соответствующих,рас.положениям, искаженных символов в последовательности 5 у, и кроме того, на д - 1 у местах, на которых корректором правильные символы были заменены на обратные. Здесь, как и в дальнейшем, предполагаегся сумми рование элементов векторов по модулю два.Для характеристики качества исправления ошибок в кодовых комбинациях 5 предлагается вычислять проверочную строку (вект У 5 у ли все 5,т, = 5,=25кодирования,(вектор) длинволов О. Есл5 гй - 5 гл + 5 принятого способа редла ющвм ступи строк ение аемого устроистваВначале раздельших,из канала ков корректоре ошибок известным гдю и из Л/пнацийисправ Известны устройства для исправления ошибок при,итеративном кодировании, описываемом двумерной матрицей с кодом по сгрокам, исправляющим ошибки, и по столбцам, обнаруживающим одну ошибку, содержащие блок хранения информации и блок исправления ощибок для кода, записанного по строкам.Предлагаемое устройство отличается от известных тем, что выход строки итеративного кода блока исправления ошибок подключен ко входам сумматора по модулю два всех строк, кода и перемножителя, к другому входу которого подсоединен выход сигнала вектора ошибки блока исправления ошибок, а выход перемножителя соединен через блок сравнения с блоком номеров, разрешающим запись в этот блок номера строки из блока управления, и, кроме того, выход импульсов кодовой комбинации блока исправления ошибок соединен со входом полусумматора, другой вход которого через ключ, подсоединенный к выходу блока номеров, связан с выходом сумматора.Это позволяет упростить аппаратурную реал,изацию.Принцип работы п гзаключается в следуно в каждой о вдовых комби ( )выполняегся л О - последовательность состоящая только из симдля одной комбинации для всех остальныхЗоны векторов Векторы 00 00 11 11 11 11 00 0. 0 00 00 Покажем, что знание вектора Ь и векторов ошибок ,= 5,+5;, для каждой комбинации 5 йозволяет найти комбинацию 5 а значит и искомую 5,= 5 и+ ы = 5 м+1Для этого рассмотрим Ж гипотез, каждая из которых состоит в предположении, что г = 1(1= 1, 2, У) . Каждой 1-ой гипотезе соответствует определенное число символов М изменяемых при декодирова)нии,на обратные, Согласно критерию приема по максимуму правдоподобия должна быть принята такая гипотеза, которая приводит к минимальному М , Для величи)ны М, справедливо соотношейие Л,= Т(,) ) Т(У +Е,) - Р(У;),=1где Г (,) - число единиц (вес) в вектореУ,. Учитывая, что 1-е слагаемое для всех М )одинаковоследует предпочесть 1-ую гипотезу,для которой величинав ,. =(и, + е) - к (ъ,) (1м иним альна.Для нахождения способа вычисления бРразобьем последовательность (вектор)состоящую из и символов, на четыре зоны К 1 зоне отнесем позиции, на которых в последовательностях Л и Ъ; одновременно расположены нулевые символы; в зоне 11 в последовательности Е - единицы, а в последовательности Ъ, - )нули; в зоне П 1 в обоих последовательностях единицы; в зоне 1)в последовательности Ь - нули, а в последовательносги У, - единицы. ТогдаУ(Ъ;) = 1, + 1У(Ъ, + Е) = У, + У, = 1 - Е, + Р (2 где 1; - число позиций в 1-ой зоне,1= В (Е) - 12+ 3Из выражений (1) и (2) получимб 1 Р = 1 - 21.Таким образом, минимальному бУ; соответствует максимальное 1 з, для нахождения которого следует перемножить последовательности Р, и А с помощью схемы совпадения,Изложенный способ позволяет исправлять все ошибки кратности не более д - 1, что означает пол)ное использование корректирующей способности итеративного кода. 5 10 15 20 25 зо З 5 40 45 50 55 60 65 Предлагаемое устройство отличается тем, что импульсы кодовой комби)нации, являющейся строкой итеративного кода, с выхода блока исправления ошибок поданы на сумматор для нахождения проверочной строки, а импульсы сигнала проверочной строки совместно 1 с сипналом вектора ошибок, вырабатываемым в блоке исправления ошибок, поданы на перемножитель, выход которого соединен через блок сравнения, оты)скивающим последовательности с наибольшим числом единиц, с блоком номеров для разрешения записи в этот блок номера строки из блока управления, и, кроме того, импульсы кодовой ком бинации с блока исправле)ния ошибок поданы на полусумматор, к другому входу которого через ключ, управляемый сигналом с блока, номеров, подсоединен выход сум)м атор а.Данные отличительные признаки позволяют упростить устройство исправления ошибок в итеративном коде,На чертеже изображена функциональная схема предлагаемого устройства, где 1 - блок управления; 2 - блок хранения информации; д - блок исправления ошибок; 4 - выход кодовой комбинации; 5 - сумматор; б - выход вектора ошибок; 7 - перемножитель; 8 - блок сравнения; 9 - блок номеров; 10 - выход номера сх)роки; 11 - полусумматор; 12 - выход импульсов считывания; И - ключ.Вся процедура исправления ошибок в итеративном коде выполняется за три этапа, каждый из которых состоит из (Л+1) циклов, имеющих длительность ат, где т - длительность элементарной посылки.Все необходимые временные метки создаются в блоке управления 1, на )который в начале сеанса связи поступает аинхроимпульс, устанавливающий его в исходное состояние. На первом этапе зашумленные комбинации кода первой итерации 5 последова- тельно поступают из канала на блок хранения информации 2 и (для выполнения операции и)справления ошибок в коде первой итерации) на блок 3, на выходе 4 которого с задержкой на время пт формируется кодовая комбинация 5,),. Выход 4 подан на сумматор 5, в котором находится проверочная строка5. Таким образом, в итоге первого1=1этапа в сумматоре 5 находится проверочная строка Л, а в блоке хранения информации запоминающая все Ж строк итеративного кода.На втором этапе комбинация 5; считывается без разрушения с выхода блока 2 и поступает на блок 3, на выходе б которого с задержкой на т формируется вектор ошибокпоступающий на перемножитель 7. На выходе сумматора 5 в каждом цикле второго и третьего этапов выдается в последовательном коде вектор Ь, который поступает на другой вход перемножителя. Поэтому на вы 25125365 ходе первмножителя 7 в (1+1)-ом цикле образуется последовательность Р 1 -- Р 1., которая поступает на блок сравнения 8. В блокецравнения определяется число единиц гнаходящихся в каждой последовательностиР 1. Если г 1 больше числа г (1(1), хранящегося в его узле памяти, то на выходе блока сравнения появляется импульс, поступающий на блок номеров 9, и,в узел памятизаписывается число г . Если же г, (г тона выходе блока 8 импульс не образуется и вузле памяти остается записанным число г,.Одновременно с образованием последовательности Р 1 с блока управления 1 в блок номеров 9 в параллельном коде подается на1+1-ом цикле число 1, которое только при наличии импульса на выходе блока 8 записы.вается в узел блока 9. Таким образом, в кон.це второго этапа в блоке номеров оказывается записанным число 1, соответствующеепоследовательности Р 1 с наибольшим числомеди,ниц,На третьем этапе вновь осуществляетсясписывание кодовых комбинаций 5 с блока2 в блок исправления ошибок, с четвертоговыхода которого комбинации 5 через полусумматор 11 поступают на выход устройства.Одновременно с блока 1 в блок 9 поступаютимпульсы считывания, обеспечивающие выдачу на выходе блока 9 сигнала, который замыкает ключ 13 во время поступления на полусумматор комбинации 5, (в 1+1-ом цикле).Поэтому импульсы последовательности проходят через ключ 13 на,вход полусумматора 11,где осуществляется сложение последовательностей 5 и 1, по,модулю два, Во всех остальных 1+1-ых циклах (1 Ф 1) ключ 13 оказывается разомкнутым, и комбинации 51 проходят на выход устройства без изменения.Перейдем к более детальному описаниюфункциональной схемы устройства. Блок 1содержит генератор опорных импульсов 14,выход которого подсоединен к последовательно включенным счетчику тактовых импульсов (на 32 числа) узла 15, счетчику элементарных посылок (на и число) узла 1 б, счетчику циклов (на Л+1 чисел) узла 17 и счетчику режимов (на 3 числа) узла 18. В начале сеанса связи в блок 1 поступает синхроимпульс, устанавливающий все счетчики в нулевое состояние, причем счетчик тактовыхимпульсов обеспечивает привязку временныхметок устройства к моменту приема информации с погрешностью, не превышающейНа перовом этапе комбинации кода 5 последовательно поступают из канала черезячейку 19 ИЛИ на накопитель 20, входящий в блок хранения информации, и одновременно через ячейку 21 ИЛИ на корректор22, находящийся в блоке исправления ошибок.На выходе 4 корректора 22 с задержкойна время т формируется кодовая комбинация 5 полученная в итоге выполнения 5 10 15 20 25 30 35 40 45 50 55 60 операции исправления ошибок. Во время первого этапа на ячейку 23 И с блока управления 1 поступает разрешающий потенциал, и последовательность 5 проходит с выхода корректора через полусумматор 24 на вход п-разрядного регистра 25. В течение всего времени работы устройства на регистр 25 со счетчика узла 15 поступают на тридцать первом такте продвигающие импульсы, Выход регистра 25 соединен со входом полусумма- тора 24. На втором этапе комбинации 51 считываются,с выхода накопителя через ячейку 26 И и,вновь поступают на его вход, а также подаются на вход корректора. На ячейку 2 б со счетчика узла 18 поступает разрешающий потенциал во время второго и третьего этапов. С выхода корректора 27 через ячейку 28 И, на которую во время второго этапа со счетчика узла 18 поступает разрешающий потенциал, на перемножитель 7 поступает вектор ошибок 1 г, образуемый в корректоре для каждой комбинации 51. Одновременно на вход перемножптеля подаются с регистра 25 импульсы последовательносги 1. и на его выходе образуется последовательность Р 1 - - 1 Ь, которая поступает на блок сравнения 8, рабогающпй следующим образом. Перед началом второго этапа в счетчике памяти 29 записано нулевое число (счетчик находится в первом состоянии), которое через ключи 30, 31 (в количестве, равном числу разрядов счетчика 29) параллельно в обратном коде переписывается в счетчик сравнения 32. Ключи 30, 31 открываются первым тактовым импульсом первой элементарной посылки каждого цикла, который поступает со счетчиков узлов 15 и 1 б через дешифратор 33.Двоичные счетчики 29 и 32 имеют 5 разрядов, где величина определяется условием 2 - (х-(2, Итак, в начале второго этапа в счетчике 29 находится число О, а в счетчике 32 - число 2 - 1. Дешифратор 34 выдает разрешающий потенциал при наличии в счетчике сравнения только числа 2 - 1. Поэтому во время второго цикла второго этапа ячейка 35 И пропускает сигнал с выхода перемножителя на вход счетчика памяти, а ячейка 36 И благодаря инвертору 37 блокирует вход счетчика сравнения 32.Пусть в векторе Р, находится г, единиц. Тогда к началу третьего цикла в счетчике памяти будет находиться число г,. После первого такта первой посылки третьего цикла в счетчик сравнения 32 будет записано через ключи 30, 31 число 2 - 1 - г. Если г,=О, то поведение блока сравнения в третьем цикле такое же, как во втором. Поэтому полагаем, что г,ФО. Тогда во время второго цикла с ячейки 35 И на выходе блока сравнения 8 проходит г, импульсов, После первого такта первой посылки третьего цикла на выходе дешифратора 34 разрешающий потенциал отсутствует, благодаря чему сигнал с выхода перемножителя будет проходить только черезячейку 3 б И на вход;счетчика оравнения. Если в третьем цикле г(гто во время всего третьего цикла импульсы не будут поступать на вход счетчика памяти, а значит и на выход блока сравнения. После первого такта первой посылки четвертого цикла в счетчике сравнения вновь оказывается число 2 - г, - 1. Если г,)г то импульсы с перемножителя 7, начиная )с (г,+1) импульса, проходят в счетчик памяти, Тогда в конце третьего цикла в счетчике памяти оказывается число г и т. д. Таким образом, если в текущем 1-ом цикле на выходе перемножителя появляется число импульсов г 1) г(где гчисло, находя. щееся в счетчике памяти), то на выходе блока сравнения появляется, по крайней мере, первый импульс, а в счетчик памяти записывается число г 1, Импульс с блока сравнения поступает на,ключи 38 и 39 (по одному ключу на каждый разряд счетчика узла 17) в блоке номеров, и число, находящееся в счетчике узла 17, параллельно в обратном коде записывается в счетчик 40. Двоичные счетчики 17 и 40 имеют И раз(рядов, где величина И определяется,соотношением 2 г-(У+ 1(2 И. Если для некоторой комбинации Я величина г 1)г(г =1,2 1 - 1, 1,1+1 Л/), то во время (1+1) цикла, ковда в,счетчике 17 находится число 1, в счетчик 40 будет записано число 2 д - 1 - 1 и это число окажется в нем до конца второго этапа.На третьем этапе .вновь осущеспвляется описывание векторов 51 с накопителя в корректор, с,выхода 4 которого комбинации 51 через полусумматор 11 поступают на выход устройства,Одновременно на вход счетчика 40 со счетчика узла 1 б через ячейку 41 И, на которую на третьем этапе со счетчика узла 18 поступает разрешающий потенциал, проходят импульсы, соответствующие тридцать второму такту послвдяей посылки каждого цикла, В конце 1-го цикла в счетчике 40 окажется записанным число 2 О - 1, что фиксируется выдачей,на время (1+1) цикла с дешифратора состояния счетчика 42 разрешающего потенциала на ключ 13.Благодаря этому на (1+1) -ом цикле навход полусумматора 11 проходит последовательность Ь, которая складывается по модулю два с комбинацией 51,В заключение отметим, что одновременно 10 со счетчиками узлов 15 - 18 с помощью синхроимпульса,выполняется установка в нулевое,состояние счетчика 29 и стирание информации в регистре 25, а для синхронизации работы накопителя и корректора на них по даются сигналы со счетчиков узлов 15 и 1 би только на накопитель разрешающий потенциал со счетчиков 17 через дешифратор 43 во время 1 - М цикла каждого режима.20 Предмет изобретенияУстройство для исправления ошибок приитеративном кодировании, описываемом двумерной матрицей с кодом по строкам, исправляющим ошибки и по столбцам, обнаружи вающим одну ошибку, содержащее блок хранения информации и блок исправления ошибок для кода, записанного по строкам, отличаощееся тем, что, с целью упрощения аппаратурной реализации, выход строки ите ративного кода блока исправления ошибокподключен ко входам сумматора по модулю два всех стирок кода и перемножителя, к другому входу которого подсоединении выход сигнала вектора ошибки блока исправления 35 ошибок, а выход перемножителя соединен через блок сравнения с блоком номеров, разрешающим запись в этот блок номера строки из блока управления, и, кроме того, выход импульсов кодовой комбинации блока иоправ ления ошибок соединен со:входом полусумматора, другой вход которого через ключ, подсоединенный к выходу блока номеров, связан с выходом сумматора.251,253 Составитель А. А. ПлащинТехред Л, Я. Левина Редактор Э. Рубан Корректор С, М. Сигал Типография, пр. Сапунова, 2 Заказ 3927/7 Тираж 480 ПодписноеЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССРМосква Ж, Раушская наб., д. 4/5