УСТРОЙСТВО для ИСПРАВЛЕНИЯ ОШИБОК ПРИ ИТЕРАТИВНОМ КОДИРОВАНИИ Советский патент 1969 года по МПК G06F11/08 

Из1васт1ны устройства для исправления ошибок лрН ,итерати В НОМ коди ровании, описываемом двумерной матрицей с кодом по стро-кам, испра1вляющим ошибки, .и по столбцам, обнаруживающим одну ошибку, содержащие блок хранения информации и блок исправления ош,ибок для кода, заетисаиного но строкам.

Предлагаемое устройство отличается от известных тем, что выход /строки итеративного кода блока исправления ошибОК подключен ко входам сумматора по модулю два асех строк ,кода и перемножителя, к другому входу которого подсоединен выход сигнала вектора ошибки блока исправления ошибок, а выход перемиожителя соединен через блок сравнения с блоком , разрешающим запи;сь в этот блок номера строки из блока управления, и, кроме того, выход .импульсов кодовой комбинации блока исправления ошибок соединен со входом полусумматора, другой вход которого через ключ, подсоединенный к выходу блока номеров, связан с выходом сумматора.

Это тозволяет упростить аппаратурную реализацию.

Принцип работы предлагаемого устройства заключается IB следующем. Влачале раздельно в Каждой из Л поступивших из канала кодовых комбинаций (строк) Sj в корректоре выполняется исправление ошибок известным

способом. Если в строке Sj число ошибок // а, то в результате процедуры исправления оудет получена кодовая комбинация ф/ 5/л, где Sjn -комбинация, являющаяся /-ой

строкой неискаженного итеративного кода на передаче. Если же число d, то после исправления получим Sj -}-Sj , где Sj -комбинация, в которой символ «1 находится яа tj местах, соответствующих расположениям 1иокаженных сшмволов в последовательности Sj , и кроме того, на d-tj местах, на которых корректором правильные символы были за1менены на обратные. Здесь, как и в дальнейшем, предполагается суммирование элементов векторов по .модулю два. Для характеристики качества исправления ошибок в кодовых комбинациях Sj предлагается вычислять проверочную строку (векЛ

тор) 1 5. . Если все Sj/f S

то

Jit

i E

ввиду принятого способа

кодирования, где О - последовательность (вектор) длиною п, состоящая только из символов О. Если же для о.дной комбинации Покажем, чго SHaiHHe вектора L и векторов оШ:Ибок для каждой -комбинации Sj -позволяет найти комбинацию а значит и искомую S 5, -f- г(/ - rk Для этого рассмотрим Л гипотез, каждая 5 из которых состоит в предположении, что л /(/ 1,2, . . . Л). Каждой /-ОЙ гипотезе соответствует оиределенное -число оим-волов Mj , .изменяемых при декодировании ;на обiri J , ,ПИОЛ1ЫЛ UJjn Д с is. или и и сил и и iHcl ииратные. Согласно критерию приема по максимуму правдоподобия должна быть принята такая гинотеза, которая приводит « минимальному Mj . Для велич1И1НЫ Mj справедливо соотношение Иу 2 (г) + W (Vj + L}-W (Vj), где W (V i -число единиц (вес) в векторе Vj. Учитывая, что 1-е слагаемое для всех М;) одинаково, следует предпочесть /-ую гипотезу, для которой величина bWj -W(Vj + L}-W(Vj) минимальна. Для нахождения способа вычисления dW разобьем последовательность (вектор) V j состояшую из п символов, на четыре зоны К / зоне отнесем позиции, на которых в последовательностях L и V.. одновременно расположены нулевые символы; в зоне // в последовательности L -единицы, а в последовательности У.--нули; в зоне /// в обоих последовательносгтях единицы; в зоне IV в последовательности L - нули, а в последовательносри Vj - единицы. Тогда W(Vj) l, + l,, W(Vj + L)l,+ U l-l, + U,(2 где Ij - число позиций в /-ой зоне, (.2+ls. Из выражений (1) и (2) получим Wj 1-2 Is. Таким образом, минимальному dWj соответствует максимальное 4, для нахождения которого следует перемножить последовательности Vj и L с номощью схемы совнадения. Пзложенный способ позволяет исправлять Предлагаемое устройство отличается тем, что импульсы кодовой комбинации, являющейся строкой итеративного кода, с -выхода блока исправления ошибок поданы на сумматор для нахождения проверочной строки. а им-пульсы сигнала проверочной строки совместно с сигналом вектора ошибок, вы-рабатываемым в блоке исправления ошибок, поданы на перемножитель, выход которого .., uui.AU/J, I un/pUiU соединен через блок сравнения, отысшваюЩим последовательности с наибольш-им числом единиц, с блоком -номеров для разрешения записи в этот блок номера строки из блока управления, и, кроме того, импульсы кодовой комбинации с -блока исправления ошибок поданы на полусум матор, к другому входу которого через ключ, управляемый сигналом с блока номеров, подсоединен выход сумматора. Данные отличительные признаки позволягот упростить устройство исправления ошябок в итератив-ном коде. Па чертеже изображена функциональная схема -предлагаемого устройства, где ,/ - блок управления; 2 -блок хранения -информации; 3 -блок исправления -ошибок; 4 - выход кодовой комбинации; 5 - сумматор; 6 - выход вектора ошибок; 7 - перемножитель; 8 - блок сравнения; 9 - блок номеров; 10 - выход номера ст1роки; 11-полусумматор; 12- выход импульсов считывания; 13 - ключ. Вся процедура исправления ошибок в итеративном коде выполняется за три этапа, каждый из которых состоит из (N+1) циклов, имеющих длительность пт, где т - длительность элементар-ной -посылки. Все необходимые -временные метки создаются в блоке управления 1, на который в начале -сеанса связи -поступает оинхроимпульс, устанавливающий его в исходное состояние. Па первом этапе зашумленные комбинации кода первой итерации Sj последова ьно п-оступают из канала на блок .хранения информации 2 и (для выполнения операции исправления ошибок в коде первой итерации) « блок 3, на выходе 4 которого с задержкой на время гет формируется кодовая комбинация Sjii . Выход 4 иодан на сумматор 5, в котором находится -проверочная строка л/. 2 Sjf. Таким образом, в итоге первого этапа в сумматоре 5 находится проверочная строка L, а в блоке хранения информации запоминающая -все Л -строк итеративного кода. Па втором этапе комбинация Sj считывается без разрушения с выхода бло-ка 2 и поступает на блок 3, на выходе 6 которого с задержкой на пт -формируется вектор ошибок Vj , поступающий на перемножитель 7. Па выходе -сумматора 5 в каждом цикле второго

ходе перемяожителя 7 в (/+1)-ом цикле образуется последовательность Pj j L:, коrqpaH поступает на блок сравнения 5. В блоке оравнения определяется число единиц т , находящихся в каждой последовательности PJ. Бели ГУ больше чИСла г (), хранящегося в его узле памяти, то на выходе блока сравнения появляется импульс, поступающий на блок номеров 9, и -в узел памяти занисывается число г,-. Если же Гу Г;, то на выходе блока 8 импульс не образуется и в узле памяти остается записанным число г. Одновременно с образованием последовательности PJ с блока управления / в блок номеров 9 в параллельном коде подается на /-f 1-ом цикле число /, которое только при наличии им1пульса на выходе блока 8 записывается в узел блока 9. Таким образом, в конце второго этапа в блоке номеров оказывается записанным число /, соответствующее последовательности Pj с наибольшим числом единиц.

На третьем этапе вновь осуществляется списывание кодовых комбинаций Sj с блока 2 в блок исправлевия ошибок, с четвертого выхода которого комбинации 5 через полусумматор // поступают на выход устройства. Одновременно с блока / в блок 9 поступают им1пульсы считывания, обеспечивающие выдачу на выходе блока 9 сигнала, который замыкает ключ 13 во время поступления на полусумматор комбинации Sjff (в /-f 1-ом цикле). Поэтому импульсы последовательности проходят через ключ 13 на вход полусумматора 11, где осуществляется сложение последовательностей Sj и L по .модулю два. Во всех остальных г+1-ых циклах () ключ 13 оказывается разомкнутьш, и комбинации 5 проходят на выход устройства без изменения.

Перейдем к более детальному описанию функциональной -схемы устройства. Блок / содержит гене1ратор опорных импульсов 14, ыход которого подсоединен к последовательо включенным счетчику тактовых импульсов (на 32 числа) узла 15, счетчику элементарных посылок (на п чнсло) узла 16, счетчику циклов (на A/-f-l чисел) узла 17 и счетчику режимов (на. 3 числа) узла 18. В начале сеанса связи iB блок ,/ поступает синхроимпульс, устанавливающий все счетчики в нулевое состояние, причем счетчик тактовых импульсов обеспечивает привязку временных меток устройства .к моменту приема информации с погрешностью, не превышающей На первом этапе комбинации кода S j последовательно поступают 1ИЗ канала через ячейку 19 «ИЛИ на на1копитель 20, входящий в блок .хранения информации, и одновременно через ячейку 21 «ИЛИ на корректор 22, находящийся в -блоке исправления ошибок.

На выходе 4 корректора 22 с задерлской на время т формируется кодовая комбинация Sjf,, полученная в итоге выполнения

операции исправления ошибок. Во время первого этапа на ячейку 23 «И с блока управления / поступает разрешающий потенциал, и последовательность Sj проходит с выхода корректора через полусумматор 24 на вход п-разрядного регистра 25. В течение всего времени работы устройства на регис-лр 25 со счетчика узла 15 поступают на тридцать первом такте продвигающие импульсы. Выход

регистра 25 соединен со входом полусумматора 24. На втором этапе комбинации Sj считываются с выхода накопителя через ячейку 26 «И и вновь поступают на его вход, а также подаются на вход корректора. На

ячейку 26 со счетчика узла 18 поступает разрешающий потенциал во время второго и третьего этапов. С выхода корректора 27 через ячейку 28 «И, на которую во время второго этапа со счетчика узла 18 поступает

разрешающий потенциал, на перемножитель 7 поступает вектор ошибок Vj, образуемый в корректоре для каждой комбинации Sj. Одновременно на вход перемножителя подаются с регистра 25 импульсы последовательносги L и на его выходе образуется последовательность L, которая поступает на блок сравнения 8, работающий следующим образом. Перед началом второго этапа в счетчике памяти 29 записано нулевое

число (счетчик находится в первом состоянии), которое через ключи 30, 31 (в количестве, равном числу разрядов счетчика 29) параллельно в обратном коде переписывается в счетчик сравнения 32. Ключи 30, 31 открываются первым тактовым импульсом первой элементарной посылки каждого цикла, который поступает со счетчиков узлов 15 и 16 через дешифратор 33. Двоичные счетчики 29 и 32 имеют S разрядов, где величина определяется условием . Итак, в начале второго этапа в счетчике 29 находится число О, а в счетчике 32 - число . Дешифратор 34 выдает разрешающий потенциал при наличии в

счетчике сравнения только числа 2 -1. Поэтому во время второго цикла второго этапа ячейка 35 «И пропускает сигнал с выхода перемножителя на вход счетчика памяти, а ячейка 36 «И благодаря инвертору 37 блокирует вход счетчика сравнения 32.

Пусть в векторе PI находится ri единиц. Тогда к началу третьего цикла в счетчике памяти будет находиться число . После нервого такта первой посылки третьего цикла в

счетчик сравнения 32 будет записано через ключи 30, 31 число -1-ri. Если ri 0, то поведение блока сравнения в третьем цикле такое же, как во втором. Поэтому полагаем, что . Тогда во время второго цикла с

ячейки 55 «И на выходе блока сравнения 8 проходит TI имнульсов. После первого такта первой посылки третьего цикла на выходе дешифратора 34 разрешающий потенциал отсутствует, благодаря чему сигнал с выхода

ячейку 36 «И 1на (Вход ючетчика рраннения. Бели в третьем цикле , то во время всего третьего цикла импульсы не будут поступать .на ВХОД счетчика памяти, а значит и яа выход блока сравнения. После -первого такта пер.вой ПОСЫЛКИ четвертого цикла в счетчике сравиения вновь оказывается чиюло 2- -ri-1. Если , то им.пульсы с перемножителя 7, начиная с () имлульса, проходят в счетчик Памяти. Тогда в (КОнце третьего цикла в счетчике памяти оказывается чтсло г и т. д. Таким образом, если в текущем y-oiM цикле на выходе перемноЖИтеля появляется число имлульсоВ (Д л число, находящееся в 1счетчике памяти), то «а выходе блока сравнения появляется, по крайней мере, пе-рщый импульс, а в 1счетч1ик паМЯти записывается число гj . Имоульс с блока оравнения поступает «а ключи 38 и 39 (по одному ключу «а каждый разряд счетчика узла 17 в блоке номеров, И число, находящееся .в счетчике узла 17, параллельно в обратном коде залисываепся в счетчик 40. Двоичные счетчики 17 и 40 имеют Я разрядов, где величина И определяется ;ооотнощением . Если для некоторой комбинации Sj величина (ri,4...l-, I,I+-...N), то во время (/+1) цикла, когда в очетчи1ке 17 находится число J, в счетчик 40 будет записано ЧИсло « это чнсло окажется в нем до конца второго этапа.

На третьем этапе вйовь осуществляется списывание векторов 5у с «аколителя в корректор, с (Выхода 4 которого комбенащии S, полусумматор 11 поступают на выход устройства.

Одновременно на вход Счетчика 40 со счетчика узла 16 через ячейку 41 «И, на которую на третьем этале ico счетчика узла 18 поступает разрещающий потенциал, строходят ИМпульсы, соответствующие тридцать второму такту последней посылки каждого цикла. В конце /-1ГО ци1кла 0 счетчике 40 окажется

записанным число 2 - 1, что фиксируется выдачей на время (/+1) цикла с дешифратора состояния счетчи;ка 42 разрешающего потенциала на ключ 13.

Благодаря атому на (/-fl)-OM цикле на вход полусумматора // проходит последовательность L, которая складывается по модулю два с комбинацией 5 .

В заключение отметим, что одновременно

со счетчиками узлов 15-18 с помощью синхроимпульса .выполняется установка в нулевое состояние счетчика 29 и стирание информации в регистре 25, а для синхронизации работы накопителя и корректора на них иодаются сигналы со счетчиков узлов 15 и 16 и только на накопитель разрешающий потенциал со счетчиков -17 через дешифратор 43 во эремя I-Л цикла каждого режима.

Предмет изобретения

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

ошибок, а выход перемножителя соединен через блок сравнения с блоком номеров, разрешающим запись в этот блок (номера строки из блока управления, и, кроме того, выход импулысов кодовой комбинации блока иоправления ошибок соединен со, входом полусумматора, другой вход которого через ключ, подсоединенный к выходу блока нО:Меров, связан с выходом сумматора.