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

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

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

25I253

Сома Советских

Социалистических

Республик с

Зависимое от авт. свидетельства №

Заявлено 28.111.1968 (№ 1228748/18-24) с присоединением заявки №

Приоритет

Опубликовано 26Х!11.1969. Бюллетень № 27

Дата опубликования описания 4.11.1970

Кл. 42ml, I I (08

МПК С 06f

УДК 681.326.75(088.8) Комитет ло делам изобретений и открытий при Совете Министров

СССР

Автор изобретения

Л. Д. Кислюк

Заявитель

УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОШИБОК

ПРИ ИТЕРАТИВНОМ КОДИРОВАНИИ

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

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

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

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

2 способом. Если в строке S j число ошибок

t> и, то в результате процедуры исправления будет получена кодовая комбинация рул =5туу, где Sg, — комбинация, являющаяся 1-ой строкой неискаженного итеративного кода на передаче. Если же число a(t j

S» — комбинация, в которой символ «1» находится на t j местах, соответствующих,расположениям, искаженных символов в последовательности $у, и кроме того, Hà d — t> местах, на которых корректором правильные символы были заменены на обратные. Здесь, как II в дальнейшем, предполагаегся суммирование элементов векторов по модулю два.

Для характеристики качества исправления ошибок в кодовых комбинациях S предлагается вычислять проверочную строку (век1V тор) L=g 5 .. Если все S,.p = S,, то

/=1 — бт„ = 0 ввиду принятого способа

25 кодирования, где Π— последовательность (вектор) длиною и, состоящая только из символов О. Если же для одной комбинации

S = $,„+ S а для всех остальных зо S,,=S,.„, TTo L=S„.

251253

Зоны векторов

Векторы

0...0

0...0 1...1

1...1 1...1

1...1 0...0

О. 0

0...0

0...0

VjyL

Покажем, что зна ние вектора L и векторов ошибок Г, = 5, + 5» для каждой комбинации S йозволяет найти комбинацию S,, а значит и искомую 5«5,), +,d =,1,. + 1.

Для этого рассмотрим N гипотез, каждая из которых состоит в предположении, что г=/(1=1,2,... У). Каждой 1-ой гипотезе соответствует определенное число символов

М,, изменяемых при декодирова(нии,на обратные. Согласно критерию приема по максимуму правдоподобия должна быть принята такая гипотеза, которая приводит к миниiiIanI 11o»ly М . Для величи)ны М, справедливо соотношейие

Л) = W(V,) )- W(V + (.) — W(V,), j=1 где W (V ) — число единиц (вес) в векторе

V< Учитывая, что 1-е слагаемое для всех М ) одинаково,,следует предпочесть 1-ую гипотезу, для которой величина

| Wj = W(Vj+ L) — W(V) (1 м иним альна.

Для нахождения способа вычисления бГ разобьем последовательность (вектор) состоящую из и символов, на четыре зоны

К 1 зоне отнесем позиции, на которых в последовательностях L u Vj одновременно расположены нулевые символы; в зоне 11 в последовательности L — единицы, а в последовательности Vj — (нули; в зоне 111 в обоих последовательностях единицы; в зоне I V в последовательности L — нули, а в последовательносги U — единицы. Тогда

W(V) =l,+l,, W(Vj + L) = 1, + 1, = 1 — 1, + 1,, (2 где 1; — число позиций в j-ой зоне, 1" (1 ) 12+ l3.

Из выражений (1) и (2) получим

6W = l — 21 .

Таким образом, минимальному 6Wj соответствует максимальное lq, для нахождения которого следует перемножить последовательности V u L с помощью схемы совпадения.

Изложенный способ позволяет испра влять все ошибки кратности не более d — 1, что означает пол)ное использование корректирующей способности итеративного кода.

Зо

З5

Предлагаемое устройство отличается тем, что импульсы кодовой комби)нации, являющейся строкой итера pllвного кода, с выхода блока исправления ошибок поданы на сумматор для нахождения проверочной строки, а импульсы сигнала проверочной строки совместно с сипналом вектора ошибок, в Ipaoaтываемым в блоке исправления ошибок, поданы на перемножитель, выход которого соединен через блок сравнения, oTbllcKiHBBIQщим последовательности с наибольшим числом единиц, с блоком номеров для разрешения записи в этот блок номера строки из блока управления, и, кроме того, импульсы кодовой комбинации с блока исправления ошибок поданы на полусумматор, к другому входу которого через ключ, управляемый GHIналом с блока, номеров, подсоединен выход с ум(м атор а.

Дан ные отличительные признаки позволяют упростить устройство исправления ошибок в итеративном коде.

На чертеже изображена функциональная схема предлагаемого устройства, где 1 — блок управления; 2 — блок хранения информации;

8 —; 4 — выход кодовой комбинации; 5 — сумматор; б — выход вектора ошибок; 7 — перемножитель; 8— блок сравнения; 9 — блок номеров; 10 — выход номера ст)роки; 11 — полусумматор; 12— выход импульсов считывания; И вЂ” ключ.

Вся процедура исправления ошибок в итеративном коде выполняется за три этапа, каждый из которых состоит из (Л + 1) циклов, имеющих длительность ат, где т — длительность элементарной посылки.

Все необходимые временные метки создаются в блоке управления 1, на )который в начале сеанса связи наступает аинхроимпульс, устанавливающий его в исходное состояние. На первом этапе зашумленные комбинации кода первой итерации Sj последова- тельно поступают из канала на блок хранения информации 2 и (для выполнения операции исправления ошибок в коде первой итерации) на блок 3, на выходе 4 которого с задержкой на время пт формируешься кодовая комбинация S». Выход 4 подан на сумматор 5, в котором находится проверочная строка

S». Таким образом, в итоге первого

j 1 этапа в сумматоре 5 находится проверочная строка L, а в блоке хранения информации запоминающая все N строк итеративного кода.

На втором этапе комбинация S . считывается без разрушения с выхода блока 2 и поступает на блок 8, на выходе б которого с задержкой на т формируется вектор ошибок поступающий на перемножитель 7. На выходе сумматора 5 в каждом цикле второго и третьего этапов выдается в последовательном коде .вектор L, который поступает на другой вход перемножителя. Поэтому на вы251253

65 ходе перомножителя 7 в (j+1)-ом цикле образуется последовательность Р— — V . L, которая поступает на блок сравнения 8. В блоке сраВнения определяется число единиц r находящихся в каждой последовательности

Р>. Если rj больше числа rg (i(j), хранящегося в его узле памяти, то на выходе блока сравнения появляется импульс, поступающий на блок номеров 9, и,в узел памяти записывается число ri. Если же r; (r<, то на выходе блока 8 импульс не образуется и в узле памяти остается записанным число г,.

Одновременно с образованием последовательности Р1 с блока управления 1 в блок номеров 9 в параллельном коде подается на

j+1-ом цикле число 1, которое только при наличии импульса на выходе блока 8 записывается в узел блока 9. Таким образом, в конце второго этапа в блоке номеров оказывается записанным число j, соответствующее последовательности Р> с наибольшим числом еди,ниц.

На третьем этапе вновь осуществляется списывание кодовых комбинаций S с блока

2 в блок исправления ошибок, с четвертого выхода которого комбинации S>p через полусумматор 11 поступают на выход устройства.

Одновременно с блока 1 в блок 9 поступают импульсы считывания, обеспечивающие выдачу на выходе блока 9 сигнала, который замыкает ключ 18 во время поступления на полусумматор комбинации S» (в j+1-ом цикле).

Поэтому импульсы последовательности проходят через ключ 13 на,вход полусумматора 11, где осуществляется сложение последовательностей S» и L по,модулю два. Во всех остальных i+1-ых циклах (i ®j) ключ 18 оказывается разомкнутым, и комбинации S» проходят на выход устройства без изменения.

Перейдем к более детальному описанию функциональной схемы устройства. Блок 1 содержит генератор опорных импульсов 14, выход которого подсоединен к последовательно включенным счетчику тактовых импульсов (на 32 числа) узла 15, счетчику элементарных посылок (на и число) узла 1б, счетчику циклов (на N+1 чисел) узла 17 и счетчику режимов (на 3 числа) узла 18. В начале сеанса связи в блок 1 поступает синхроимпульс, устанавливающий все счетчики в нулевое состояние, причем счетчик тактовых импульсов обеспечивает привязку временных меток устройства к моменту приема информации с погрешностью, не превышающей

На перовом этапе комбинации кода 5 . последовательно поступают из канала через ячейку 19 «ИЛИ» на накопитель 20, входящий в блок хранения информации, и одновременно через ячейку 21 «ИЛИ» на корректор

22, находящийся !в блоке исправления ошибок.

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

60 операции исправления ошибок. Во время первого этапа на ячейку 28 «И» с блока управления 1 поступает разрешающий потенциал, и последовательность Si проходит с выхода корректора через полусумматор 24 на вход и-разрядного регистра 25. В течение всего времени работы устройства на регистр 25 со счетчика узла 15 поступают на тридцать первом такте продвигающие импульсы. Выход регистра 25 соединен со входом полусумматора 24. На втором этапе ком бина ции S> считываются,с выхода накопителя через ячейку 26 «И» и,вновь поступают на его вход, а также подаются на вход корректора. На ячейку 2б со счетчика узла 18 поступает разрешающий потенциал во время второго и третьего этапов. С выхода корректора 27 через ячейку 28 «И», на которую во время второго этапа со счетчика узла 18 поступает разрешающий потенциал, на перемножитель

7 поступает вектор ошибок V1, образуемый в корректоре для каждой комбинации S>.

Одновременно на вход перемножителя подаются с регистра 25 импульсы последовательносги L и на его выходе образуется последовательность Р1 -— V> L, которая поступает на блок сравнения 8, рабогающпй следующим образом. Перед началом второго этапа в счетчике памяти 29 записано нулевое число (счетчик находится в первом состоянии), которое через ключи 30, 81 (в количестве, равном числу разрядов счетчика 29) параллельно в обратном коде переписывается в счетчик сравнения 82. Ключи 80, 81 открываются первым тактовым импульсом первой элементарной посылки каждого цикла, который поступает со счетчиков узлов 15 и 1б через дешифратор 88.

Двоичные счетчики 29 и 82 имеют S разрядов, где величина определяется условием

2 — (х (2 . Итак, в начале второго этапа в счетчике 29 находится число О, а в счетчике 82 — число 2 — 1. Дешифратор 84 выдает разрешающий потенциал при наличии в счетчике сравнения только числа 2 — 1. Поэтому во время второго цикла второго этапа ячейка 35 «И» пропускает сигнал с выхода перемножителя на вход счетчика памяти, а ячейка 86 «И» благодаря инвертору 87 блокирует вход счетчика сравнения 82.

Пусть в векторе Р, находится r, единиц.

Тогда к началу третьего цикла в счетчике памяти будет находиться число r,. После первого raкта первой посылки третьего цикла в счетчик сравнения 82 будет записано через ключи 80, 81 число 2 — 1 — r>. Если r,=0, то поведение блока сравнения в третьем цикле такое же, как во втором. Поэтому полагаем, что r, o. Тогда во время второго цикла с ячейки 35 «И» на выходе блока сравнения 8 проходит г, импульсов. После первого такта первой посылки третьего цикла на выходе дешифратора 34 разрешающий потенциал отсутствует, благодаря чему сигнал с выхода перемножителя будет проходить только через

251253 ячейку 8á «И» на вход;счетчика оравнен ия.

Если в третьем цикле г (г„то во время всего третьего цикла и мпуль сы не будут поступать на вход Ic÷åò÷èêà памяти, а значит и на выход блока сравнения. После первого такта первой посылки четвертого ци|кла в счетчике сравнения вновь оказывается число 2 — r — 1.

Если г,)г,, то импульсы с перем ножителя 7, нач иная с (r,+1) импульса, проходят в счетчик памяти. Тогда в конце третьего цикла B счетчике памяти оказывается число r и т. д.

Таким образом, если в текущем 1-ом цикле на выходе перемножителя .появляется число импульсов г1) г„(где г„число, находящееся в счетчике памяти), то на выходе блока сравнения появляется, по крайней мере, пер вый импульс, а в счетчик памяти запи сывается число r1. Им пульс .с блока сравнения поступает на,ключи 88 и 89 (по одному ключу на каждый разряд счетчика узла 17) в блоке номеров, и число, находящееся .в счетчике узла 17, параллельно в обратном коде записывается в счетчик 40. Двоичные счетчики 17 и 40 имеют И раз рядов, где величина И определяется;соотношением 2 г- (N+ 1(2тт.

Если для некоторой комбинации SJ величина г1 )«(« — — 1 2...1 — 1, i i+1.. N), то во время (j+1) цикла, ковда в счетчике 17 находится число 1, в счетчик 40 будет записано число 2 т — 1 — j и это число окажется в нем до конца второго эта па.

На третьем этапе .вновь осущес пвля ется описывание векторов 51 Ic накопителя в .корректор, с,выхода 4 которого комбинации S» через полусумматор 11 поступают на выход у стройства.

Одновременно на вход счетчика 40 со счетчика узла 1б через ячейку 41 «И», на которую на третьем этапе ico счетчика узла 18 поступает разрешающий потенциал, п роходят импульсы, соответствующие тридцать второму такту послвдяей посылки каждого цикла.

В конце 1 -го цикла в счетчике 40 окажется записанным число 20 — 1, что фиксируется выдачей,на время (j+1) цикла с дешифратора состоя н ия счетчика 42 разрешающего потенциала на ключ 18.

Благодаря этому на (j+ 1) -ом цикле на вход полусумматора 11 проходит последовательность 1„которая складывается по модулю два с комбинацией S» .

В заключение отметим, что одновременно со счетчиками узлов 15 — 18 с помощью си нхроимпульса,выполняется установка в нулевое,состояние счетчика 29 и стирание и нформаци и в регистре 25, а для си нхро низации работы накопителя и корректора на них подаются сигналы со счетчиков узлов 15 и 1б и только на накопитель разрешающий потенциал со счетчиков 17 через дешифратор 48 во время 1 — N цикла каждого режима.

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

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

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

251,253

Составитель A. А. Плащин

Техред Л. Я. Левина

Редактор Э. Рубан

Корректор С. М. Сигал

Типография, пр. Сапунова, 2

Заказ 3927/7 Тираж 480 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва Ж-35, Раушская наб., д. 4/5