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

 

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

СООИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (51)4 Н 03 М 13/00

ГОСУДАРСТЗЕННЫЙ КОМИТЕТ

flQ ИЗОБРЕТЕНИЯМ И (ЛНРЬй ИЯМ

APH ГИНТ СССР

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

И АВТОРСНОМЪ СВИДЕТЕЛЬСТВУ (21) 3984550/24-24 (22) 29.11.85 (46) 23. 12. 88. Бюл. И 4? (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) Ю.Н.Жураковский, В.Н.Полторак, Л.И.Рай и В.Н.Кузнецов (53) 681.325(088.8) (56) Натент США Ф 3891969, кл. 6 06 Р 11/16, опубпик. 1975.

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

В 794728, кл. Н 03 И 13/00, 1981. (54) (57) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ

С КОРРЕКЦИЕЙ ОШИБОК, содержащее первый регистр, выходы которого подключены K первым входам первого сумматора и информационным входам второго регистра, выходы которого подключены к первым входам второго сумматора и информационным входам третьего регистра, первые и вторые выходы которого соединены соответственно с входами формирователя контрольных разрядов и первыми входами блока сумматоров, блок деления и блок элементов

И, выхода которого соединены с вторьв«и входами блока сумматоров, выходы которого являются выходами устройI

Изобретение относится к вычислительной технике и макет использоватьв ся в системах передачи и обработки цифровой информации.

Цель изобретения - упрощение уст" ройства..ЛО„, 1446695 А1 ства, первые и вторые выходы формирователя контрольных разрядов подключены к вторым входам соответствующих сумматоров, выходы которых соединены с соответствующими входами блока деления, информационные входы первого регистра являются информационными входами устройства, тактовые входы .регистров объединены и являются тактовым входом устройства, о т л ич а ю щ е е с ÿ тем, что, с целью упрощения устройства, в него введены четвертый регистр, первый и второй счетчики импульсов и элемент И, выход которого соединен с управляющим входом второго счетчика импульсов и так- а ф товым входом четвертого регистра, инфоРмационные входы которого лодкыеве- Q) ны к выходам первого сумматора, выходы блока деления соединены с установочными входами второго счетчика импульсов, выходы которого и выходы четвертого регистра подкюночены соответственно к первым и вторым входам блока эле- yaaa ментов И, выходы первого счетчика им- «фь пульсов соединены с первыми входами ф элемента И, второй вход которого обьединен со счетнычи входами счетчиков импульсов и подключен к тактовому с© входу устройства.

2

На фиг. 1 приведена схема устройства для декодирования с коррекцией ошибок; на фиг. 2 — формирователь контрольных разрядов; на фиг, 3 — укрупненный алгоритм функционирования устройства« на фиг, 4 — пространст1446695

101111111

000001111

000110011

011010101

3Î

011234567

45 венно-временная диаграмма работы уст.ройства.

Устройство для декодирования с коррекцией ошибок содержит первый—

5 четвертый регистры 1-4, формирователь 5 контрольных разрядов, первый

6 и второй 7 сумматоры, блок 8 деления, первый 9 и второй 10 счетчики импульсов, блок 11 элементов И, эле- ip мент И 12 и блок 13 сумматоров. Кроме того, на фиг. 1 обозначены информационные 14 и тактовые 15 входы и выходы 16.

Регистры 1, 2 и 4 — параллельные 15

m-разрядные, где m — разрядность кодового символа в декодируемом коде.

Регистр 3 представляет собой кразрядный регистр сдвига, где к— число информационных символов в кодо- 20 вом слове, причем каждый его разряд представляет собой параллельный регистр, аналогичный регистру 1.

Формирователь 5 контрольных разрядов выполнен в соответствии с кон- 25 кретно используемым кодом. Для систематического кода с основанием q=2 и проверенной матрицей размера

rxn=2x9; г=п-k, n=k+2=2 +I, каждую кодовую комбинацию которого представляют кодовым вектором Х (р,р х х,х,х4х х,х,), где р - первая группа контрольных разрядов р вторая группа контрольных раэрядов1 х . — i-я группа разрядов данных, про40 верочные элементы вычисляют на основании общего матричного уравнения

НхН = 0 в соответствии с равенствами х +х, +х +х,!.+х,+х, +х, 1 1 р = х,+2х +Зхз+4х +5х,+бх,+7х„ где m = 3 ° n = 9; k = 7; О - нуле50 вой вектор-столбец.При этом операции над элементами матрицы р, и х . выпол-! 1 няют как над элементами конечного поля GF(q) порядка q = 2 = 8, представляя каждый из них в виде полинома не вьппе второй степени, либо группой двоичных коэффициентов этого полинома, либо его восьмеричным номером.

В предлагаемом устройстве хранение, передачу от блока к блоку и обработку этих элементов осуществляют именно в виде (!п=3)-разрядных групп двоичных коэффициентов. При этом матрицу

H можно в двоичной форме представить следующим образом:

В соответствии с выражениями для р„ и р в приведенном примере формирователь 5 контрольных разрядов (фиг. 2) содержит первый канал суммирования группы разрядов данных на сумматорах

17, второй канал суммирования взвешенных групп разрядов данных (каждая из которых умножена на свой коэффициент-константу) на сумматорах 18 и шесть -блоков 19-24 умножения на константы от 2 до 7.

Сумматоры 6 и 7 и блок 13 сумматоров производят суммирование по модулю два.

Блок 8 деления может быть реализован на постоянном запоминающем устройстве (ПЗУ), в котором записана соответствующая таблица деления элементов конечного поля GF(q) порядка q=2

Счетчики 9 и 10 имеют емкость n =

=k+ 2=2 +1.

Сумматоры 17 и 18 (фиг. 2) осуществляют суммирование по модулю два.

Блоки 19-24 умножения на соответствующую константу осуществляют умножение элемента конечного поля на константу и могут быть реализованы на

ПЗУ либо в виде дешифратора с шифратором, либо на логических элементах путем синтеза методом диаграмм Вейча.

Так, например, блок 22 умножения на константу 5 имеет следующую таблицу истинности (в двоичном представлении):

Синтез методом диаграмм Вейча дает Булевы выражения для выходных раз 446695

5 рядов блока ?2: f = у у +у у

2 3 13

= уо f = у °

Работа устройства основана на выполнении алгоритма декодирования с

5 коррекцией ошибки . Укрупненно этот алгоритм представляют в виде следующей процедуры (фиг. 3):

1, Формируют в декодере две группы р и р,, контрольных разрядов из к информационных групп разрядов х;, содержащихся в регистре 3.

2. Сравнивают одно ыенные группы контрольных разрядов р и р с выхо2 дов формирователя 5 контрольных раз- 15 рядов и р* и р* с выходов регистров

1 1

1 и 2 посредством сумматоров 6 и 7 и получают две группы разрядов проверочного синдрома S, и S < для данной кодовой комбинации. При этом, ес- 20 ли в одной из k-m-разрядных групп регистра 3 произошла любая ошибка, то первая группа разрядов S синдро1 ма представляет со бой величину ошибки е, а вторая S — произведение 25 величины ошибки г; на номер L искаженной позиции в кодовой комбинации.

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

35 контрольных разрядов необязательно.

3. Делят величину S, представленную второй группой разрядов синдрома, на величину ошибки е = S и оп1 ределяют номер Ь искаженной позиции щ (группы разрядов).

4. Корректируют искаженную группу разрядов х,, отыскивая ее по найденному порядковому номеру L и прибавляя к ней величину е ошибки в блоке 45

13 сумматоров. При этом получают истинное значение L-й группы данных х йст 3 I которая. была искажена. Каждый элемент кодовой комбинации (как информационный, так и контрольный) формируют в 50 виде группы, содержащей ш двоичных .разрядов, и ставят в соответствие одному из элементов конечного поля порядка о=2

На диаграмме работы устройства (фиг. 4) обозначено: а — тактовые импульсы; б — состояние первого счетчика; в, г — состояние первого 1 и второго 2 регистров, д-л — состояния раз"

6 рядов третьего регистра 3, м — импульсы на выходе элемента Н 12, н моменты записи величины ошибки в четвертый регистр 4;. о — момент коррекции ошибок в блоке 13, n — состояния второго счетчика 10; р .— очередность появления данных на выходах 16.

Устройство работает следующим образом.

В исходном состоянии первый счетчик 9 обнулен, состояния регистров

1-3 и второго счетчика 10 произвольные.

Пусть для примера m=3, тогда n=9.

На входы 14 устройства поочередно подают п=2 +1=9 групп m=3 двоичных разрядов, сначала информационные, затем вторую и первую группы контрольных разрядов. Под действием тактовых импульсов, например, по заднему их фронту (фиг. 4а) в регистрах 1-3 эти группы сдвигают n=9 в течение п=9 тактов, причем к=п-2=7 информационных групп помещают в регистр 3. Процесс продвижения информации в ячейках регистров 1-3 иллюстрирован на фиг.4 в-л. Ячейкам регистра 3, как и (m=3)-. разрядным двоичным группам данных, помещаемым в них, присваивают порядковые номера i, начиная с первой ячейки регистра 3 от i=1 до i=k=7 В. данном примере это порядковые номера

0,1,2,3,4,5,6,7 (на фиг. 2 это блоки х; для i = 1 7) . По окончании (n=9)-ro тактового импульса в регистре 3 оказываются все к=7 информационных (m=3)-разрядных групп данной кодовой (омбинации, которые подают на входы формирователя 5 контрольных разрядов.

Две группы контрольных разрядов р и р, сформированные. как описано выше, подают на первые входы сумматоров 6 и 7, где их суммируют с соответствующими группами контрольных разрядов р и р* из регистров 1 и 2. Ес1 ли в какой-либо из к=7 групп разрядов данных регистра 3 произошла любая .ошибка, то после окончания (п9)го тактового импульса значения (m--3)разрядных элементов синдрома на выходах сумматоров 6 и 7 будут отличны от

О. При этом значения разрядов S, на выходе сумматора 6 показывают величину ошибки е а значения разрядов Sq на выходе сумматора 7 показывают произведение величины ошибки е на номер искаженной позиции Ь. Посредством бло1446695 ка 8 деления определяют номер искаженной позиции, выполняя операцию деления величины, представленной m разрядами S с выхода сумматора 7, на вевеличину ошибки е с выхода сумматора

6. Задним фронтом 9-ro тактового импульса первый счетчик 9 устанавливают в нулевое состояние (фиг. 4á). его выходные сигналы при этом отпирают 10 элемент И 12 и разрешают тем самым очередному тактовому импульсу (фиг °

4м) осуществить установку разрядов второго счетчика 10 и регистра 4 в соответствии с поступившими на их 15 информационные входы сигналами. В этот тактовый период на входах регистра 4 присутствуют сигналы, представляющие в двоичной форме величину ошибки е, а на входах второго 20 счетчика 10 — сигналы, представляющие номер искаженной позиции в регистре . 3 (число 1,2,...,7), либо в регистре

1 (число О) в соответствии с элементами второй строки матрицы Н (фиг.4н) 25

Пусть ошибка произошла на седьмой позиции в первой кодовой комбинации.

На фиг. 4 в-л показано продвижение искаженного элемента 7. 1 в сотаве пер- 30 вой кодовой комбинации, По окончании девятого такта первый счетчик 9 устанавливают в состояние "О" (фиг .4б) и очередним тактовым импульсом (фиг.

4м) записывают в регистр 4 величину ошибки, а s счетчик 10 номер 7 (фиг.

4н). ВыходнЫми сигналами счетчика

10 в состоянии к=7 отпирают блок 11 и разрешают величине ошибки суммироваться в блоке 13 с искаженным 40 элементом 7.1 с выхода седьмой ячейки регистра 3 (фиг. 4). Скорректированные данные в виде (m-3)-разрядного числа снимают с выходов блока 13 от момента коррекции и до конца текущего тактового интервала (заднего фронта режущего тактового импульса), Очередность появления данных на выходе устройства проиллюстрирована на фиг. 4р. При этом первые семь 3-pasрядные группы являются скорректированными сигналами данных, а две последние группы - контрольные разряды, иэ которых первую группу к 1.1 устройство не способно скорректировать в случае ошибки в ней. Вторую группу контрольных разрядов не корректируют.

Как указывалось, в коррекции контрольных разрядов данного кода нет необходимости, поскольку их обычно игнорируют, Во время считывания с элементов первой кодовой комбинации по мере освобождения регистров 1-3 в них записывают новую кодовую комбинацию.

Коррекцию ошибки на другой позиции регистра 3 осуществляют аналогично.

Пусть, например, искажен элемент кода на третьей позиции второй кодовой комбинации. После записи в регистре 3 всей кодовой комбинации на выходе сумматора 6 присутствует величина ошибки, а навыходе блока8 -номер

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

1-3. При этом в предварительно установленном в состояние 3, = 011 втором счетчике 10 подсчитывают число сдвигов данных в регистрах 1-3 вплоть до состояния к=7, когда на вкод.блока 13 q выхода последней ячейки х регистра 3 поступит искаженный элемент второй кодовой комбинации, имеющий третью позицию 3.2 (в соответствии с второй строкой матрицы Н).

Выходными сигналами счетчика 10 в состоянии к=7 отпирают блок 11 и разрешают в этот момент величине ошибки . с выхода регистра 4 суммироваться в бпоке 13 с искаженным элементом 3.2 второй кодовой комбинации. Другие группы разрядов по мере их поступления на блок 13 суммируют с .е так, как первым после коррекции тактовым импульсом изменяют состояние счетчика

10 и запирают блок 11 элементов.

Если ошибка не происходит вовсе, либо произошла ошибка во второй группе контрольных разрядов, то в регистр

4 запишется величина ошибки "О" .и во время коррекции независимо от состоя ния счетчика 10 все группы разрядов, поступающие на вход блока 13, будут суммироваться с нулем, что никак их не изменит.

В предлагаемом устройстве вместо дешифратора обратной величины и блока умножения двух величин известного

1446695 устройства использован блок деления одной величины на другую, в котором в виде деления совмещено выполнение обеих названных операций. При этом по структуре, по количеству элементов и межэлементных связей блок 8 соответствует лишь блоку умножения двух величин в известном устройстве,; что приводит к существенному упрощению и экономии по меньшей мере ш многовходовых элементов И и инверторов НЕ (в общем счете 2 логических элементов) в результате исключения дешифратора обратной величины. Кроме того вместо m-входового на к= е (2 -1) выходов дешифратора номера искаженной позиции и блока вентилей иа к m-разрядных групп в известном устройстве в предлагаемом устройстве использованы второй счетчик 1() и блок 11 элементов И. Дешифратор в известном устройстве содержит m инверторов НЕ и как минимум К=(2 -1) многовходовых элементов И со сложными межэлементными связями, а блок вентилей известного устройства содержит К групп по m элементов И со сложными межэлементными связями. Эта (часть известного устройства содержит, S таким о бразом (m+2 -1+ЯК) логическкх элементов. В то же время в предлагаемом устройстве те же функции выполняют m триггеров второго счетчика (10) и ш элементов И блока 11р всего 2m элементов. Поэтому здесь выигрьпп составляет (ш+2 -1+mK-2m). Имеющийся в составе известного устройства блок сумматоров коррекции содержит к сумматоров по ш элементов ИСКЛЮЧАЮП1ЕЕ ИЛИ каждый, например, как показано на фиг.. 3, а в предлагаемом устройстве использован только один такой сумматор коррекции, в результате чего выигрыш составляет m(k-1) элементов. Дополнительные блоки предлагаемого устройства, которых нет в известном, содержат: регистр 4 величины ошибки — m триггеров, элемент И

12 - один элемент И, первый счетчик

2S 9 — (а+1) триггеров. В итоге выигрьпп составляет V k(2 +1)-(2ш+1)-1

Ь (2ш+1) (2 -2)-1 логических элементов, l

1446695

1446695

2 Ю Ф 5 б 7 Е

0 7 > 3

l7 юййу коий нааи . -. P юИая кои5инацл J « дМяя ви5жация

73 О53

22 2

2122

7.8 6.Я

1I.2 7.2

2 М.2 7.5

1.2

32 2.2

1S q

Й2 22

: Р .,1 6.1 Х! 0.1 $.1

l. кар

2172 72 б2

Ж 11

7.1ИРМ

2.7 72 2

К1

2.1 1.1 б 52

7г

31 2.1 у ll

11

I

>1 У 21

Û7 52 Ф.2

7.1

7.2

I ..

7012345б703175б7771339

6 701 ZЯ

6 1 б 7 Ф.2 .1 Е! 2.1112 К1 726.2 52),z 12 2212 Ег 1

Редактор Н.ТУпица ТехРед A. Кравчу

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

Заказ 18ОЗ Тираж 885 Подписное

БНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР !

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина,10) б.2 52 17.2

1.26.7 H

1.1 Ф 112) а11.1 27

2 22 2.2

Н 177.7