Устройство для декодирования с коррекцией ошибок Советский патент 1988 года по МПК H03M13/05 

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

Цель изобретения - упрощение устройства.

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

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

Регистры 1, 2 и 4 - параллельные m-разрядные, где m - разрядность кодового символа в декодируемом коде.

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

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

, ,

„ 10111111Ц1 l 01123456711,

каждую кодовую комбинацию которого представляют кодовым вектором X (p p x XjXjX XyXjX), где р - .первая группа контрольных разрядов Pj - вторая группа контрольных разрядовj

,X . - i-я группа разрядов данных, про варочные элементы вычисляют на основании общего мatpичнoгo уравнения НхН б в соответствии с равенствами

PI Xj+X -fX +X +Xj+X +X

p,j х,+2х j+3x3+4x4+5x,-f6xt+7x.,,

где О- нулевой вектор-столбец.При этом операции над элементами матрицы р , и х . выполняют как над элементами конечного поля GF(q) порядка q 2 8, представляя каждый из них в виде полинома не вьше второй степени, либо группой Двоичных коэффициентов этого полинома, либо его восьмеричным номером.

,40

45

Блоки 19-24 умножения на соответствующую константу осуществляют умножение элемента конечного поля на константу и могут быть реализованы на ПЗУ либо в виде дешифратора с щифра- тором, либо на логических элементах путем синтеза методом диаграмм Вейча. Так, например, блок 22 умножения на константу 5 имеет следующую таблицу истинности (в двоичном представлении):

50

55

Синтез методом диаграмм Вейча даВ предлагаемом устройстве хранение, ет Булевы выражения для выходных разпередачу от йпока к блоку и обработку этих элементов осуществляют именно в виде ()-разрядных групп двоичных коэффициентов. При этом матрицу Н можно в двоичной форме представить следующим образом:

000000000 000000000 101111111 II 000001111 000110011 011010101

t5

20

25

30

35

40

45

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

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

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

Счетчики 9 и 10 имеют емкость п k + 2 2 + 1.

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

Блоки 19-24 умножения на соответствующую константу осуществляют умножение элемента конечного поля на константу и могут быть реализованы на ПЗУ либо в виде дешифратора с щифра- тором, либо на логических элементах путем синтеза методом диаграмм Вейча. Так, например, блок 22 умножения на константу 5 имеет следующую таблицу истинности (в двоичном представлении):

Синтез методом диаграмм Вейча дарядов блока 22: f. у у +у у , i

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

1.Формируют в декодере две группы р и р, контрольных разрядов из

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

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

1 и 2 посредством сумматоров 6 и 7 и получают две группы разрядов проверочного синдрома S, и S J для данрядов третьего регистра 3; м - импульсы на выходе элемента И 12, н - моменты записи величины ошибки в четвертый регистр 4s о - момент коррекции ошибок в блоке 13j п - состояния второго счетчика 10; р - очередность появления данных на выходах 16.

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

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

Пусть для примера , тогда . На входы 14 устройства поочередно подают групп двоичных разрядов, сначала информационные, затем вторую и первую группы контрольных

ной кодовой комбинации. При этом, ее- 20 разрядов. Под действием тактовых им- ли в одной из k-m-разрядных групп пульсов, например, по заднему их фронту (фиг. 4а) в регистрах 1-3 эти группы сдвигают в течение тактов, причем информационных 25 групп помещают в регистр 3. Процесс продвижения информации в ячейках регистров 1-3 иллюстрирован на фиг.А в-л. Ячейкам регистра 3, как и ()- разряднын двоичным группам данных.

регистра 3 произошла любая ошибка, то первая группа разрядов S синдрома представляет со бой величину ошибки е , а вторая S г - произведение

величины ошибки Si на номер L искаженной позиции в кодовой комбинации. При этом речь не идет о возможной любой ошибке в первой или второй

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

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

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

Пусть для примера , тогда . На входы 14 устройства поочередно подают групп двоичных разрядов, сначала информационные, затем вторую и первую группы контрольных

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

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

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

Две группы контрольных разрядов . р и PJ, сформированные как описано выше, подают на первые входы суммато45 ров 6 и 7, где их суммируют с соответствующими группами контрольных разтинное значение группы данных х , рядов р и р, из регистров 1 и 2. Ескоторая.была искажена. Каждый элемент ли в какой-либо из групп разря- кодовой комбинации (как информацион- дов данных регистра 3 произошла лю- ный, так и контрольный) формируют в so ошибка, то после окончания ()- виде группы, содержащей m двоичных разрядов, и ставят в соответствие одго тактового импульса значения ()- разрядных элементов синдрома на выходах сумматоров 6 и 7 будут отличны от 0. При этом значения разрядов S , на

На диаграмме работы устройства 55 выходе сумматора 6 показывают величи- (фиг. 4) обозначено: а - тактовые им- ну ошибки е ,а значения разрядов 5

на выходе сумматора 7 показывают произведение йеличины ошибки е на номер искаженной позиции L. Посредством блоHoi iy из элементов конечного поля порядка .

пульсы; б - состояние первого счетчика; в, г - состояние первого 1 и второго 2 регистров; д-л - состояния разпомещаемым в них, присваивают поряд

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

входы формирователя 5 контрольных разрядов.

Две группы контрольных разрядов . р и PJ, сформированные как описано выше, подают на первые входы сумматоов 6 и 7, где их суммируют с соотетствующими группами контрольных разка 8 деления определяют номер искаженной позиции, выполняя операцию деления величины, представленной га разрядами S с выхода сумматора 7, на ве величину ошибки е с выхода сумматора 6. Задним фронтом 9-го тактового импульса первый счетчик 9 устанавливают в нулевое состояние (фиг. 46). Его выходные сигналь при этом отпирают элемент И 12 и разрешают тем самым очередному тактовому импульсу (фиг. 4м) осуществить установку разрядов второго счетчика 10 и регистра 4 в соответствии с поступившими на их информтщонные входы сигналами. В этот тактовый период на входах регистра 4 присутствуют сигналы, представляюпще в двоичной форме величину ошибки е, а на входах второго счетчика 10 - сигналы, представхгяющие номер искаженной позиции в регистре 3 (число 1,2,...,7), либо в регистре 1 (число 0) в соответствии с элементами второй строки матршрл Н (фиг.4н)

Пусть ошибка произошла на седьмой позиции в первой кодовой комбинации. Ela фиг. 4 в-л показано продвижение искаженного элемента 7.1 всотаве первой кодовой комбинации. По окончании девятого такта первый счетчик 9 устанавливают в состояние О (фигЛб) и очередным тактовым импульсом (фиг. 4м) записьшают в регистр 4 величину ошибки, а в счетчик 10 номер 7 (фиг. 4н), ВыходнМ и сигналами счетчика 10 в состоянии к«7 отпирают блок 11 и разрешают величине ошибки суммироваться в блоке 13 с искаженным элементом 7,1 с выхода седьмой ячейки регистра 3 (фиг. 4). Скорректированные данные в виде (ю-3)-разрядного числа снима}0т с выходов блока 13 от Момента коррекции и до конца те- кущего тактового интервала (заднего фронта режущего тактового импульса), Очередность появления данных на выходе устройства проиллюстрирована на фиг. 4р. При этом первые семь 3-раз- рядные группы являются скорректиро- ваншл4и сигналами данных, а две последние группы - контрольные разряды, из которых первую группу к 11 устроство не способно скорректировать в случае овтбкн в ней. Вторую группу контрольных разрядов не корректируют Как указывалось, в коррекции контрольных разрядов данного кода нет

5 0 5

0 п 5 , 5

5

необходимости, поскольку их обычно игнорируют.

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

Пусть, например, искажен элемент кода на третьей позиции второй кодовой комбинации. После записи в регистре 3 всей кодовой комбинации на выходе сумматора 6 присутствует величина ошибки, а невыходе блока8 -номер три искаженной позиции. По переднему фронту очередного тактового импульса эту информацию записывают импульсом с выхода элемента И 12 в регистр 4 и во второй счетчик 10. По текущему и следующим тактовым импульсам осуществляют выдачу данных с выходов 16 устройства получателю, а также сдвиг и запись элементов новой кодовой комбинации в регистры 1-3. При этом в предварительно установленном в состояние 3 7в 01 1 2 втором счетчике 10 подсчитывают число сдвигов данных в регистрах 1-3 вплоть до состояния , когда на вход блока 13 с выхода последней ячейки х. регистра 3 поступит искаженный элемент второй кодовой комбинации, имеющий трет1$ю позицию 3.2 (в соответствии с второй строкой матрицы Н).

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

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

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

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

k

/; p& i

/, A - A @;г e,,Le

(

1

@;г e

ж2

.L

0.J

Ж 3 и

К

л и и

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

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

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 1 V:i035, Москва, Ж-35, Раушская наб., д. 4/5

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