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

Иллюстрации

Показать все

Реферат

 

335689

ОПИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

Союз Советских

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

Республик

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

М. Кл. 6 06f 11/00

Заявлено 06.V1.1970 (№ 1447049!18-24) с присоединением заявки №, Приоритет !

Опубликовано 11 1Ч.1972. Бюллетень ¹ 13

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

СССР

УДК 681.326.7(088.8) Дата опубликования описания 18.V.1972

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

П. А. Котов

Заявитель

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

В КОДОВОЙ КОМБИНАЦИИ

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

d =2t+1.

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

d=t+1 и обнаруживает ошибки более высокой кратности.

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

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

5 вплоть до кратности t продолжается до тех пор, пока не будет получена исправленная кодовая комбинация без ошибок или с необнаруженными ошибками.

Описанный алгоритм позволяет исключить

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

15 На фиг. 1 представлена схема устройства для исправления t-кратных ошибок; tra фиг.2 — схема блока формирования полиномов ошибок.

С выхода однопороговой схемы 1 кодовая

20 комбинация, состоящая из последовательности

«О» и «1» подается на вход устр ойс тва обна= ружения ошибок 2 и в регистр памяти 8 блока входных регистров 4. После приема и символов кодовая комбинация из регистра памя25 ти 8 тактовым импульсом Тк параллельным кодом,считывается в регистр 5; и регистр 8 готов к приему следующей кодовой последовательности.

Если в принятой комбинации устройством 2

50 ошибка не обнаружена, то на его выходе сиг335689

s= c, =2 — 1, 3=1 нала не будет и триггер б остается в положении, при котором на его левом плече низкое ,напряжение и ключевые ячейки 7 и 8 закрыты.

Продвигающими импульсами Т> из регистра 5 принятая кодовая комбинация через сумматор 9 по модулю два и ячейку 10 записывается в ретистр (1 блока выходных регистров

12 и одновременно подается на вход устройства обнаружения ошибок 18. Так как в кодовой комбинации ошибка не обнаружена, то на выходе устройства 18 сигнала нет и триггер 14 под воздействием импульса с выхода инвертора 15 переходит в состояние, при котором ячейка 10 закрывает выход сумматора 9. Такое состояние продолжается до начала приема следующей кодовой комбинации, пока поступающий на второй вход триггер

14 тактовый импульс Т„не установит его в положение, при котором ячейка 10 вновь откроется.

Записанная в регистр 11 принятая кодовая комсинация переписывается в регистр lб и затем тактовым импульсом Т, передается получателюю.

Если в принятой комбинации устройством 2 обнаружена ошибка, на его выходе появляется сигнал ср, который переводит триггер б в такое состояние, при котором сигналом ячейки 7 и 8 переводятся в открытое состояние.

В результате анализа каждого принимаемого элемента кодовой последовательности, на входе двухпоротовой схемы 17 появляется сигнал «стирания» х в том случае, если принятый символ не может быть отождествлен ни с «1», ни с «0». Эти ненадежные символы (элементы) подаются в блок формирования полиномов ошибки (БПФО) 18, где записываются в соответствующие разряды регистра памяти.

Предлагаемое устройство рассчитывается на исправление 1 ошибок. Поэтому число вводимых в БФПО ошибочных (ненадежных) символов не должно превышать заданной величины t(d — 1, где d — кодовое расстояние.

В соответствии с этим емкость счетчика 19 выбирается равной t. Поэтому при появлении ошибок в количестве r)t выходной импульс от счетчика 19 переводит триггер 20 в положение, при котором ключевая ячейка 21 закрыта и подача ошибочных символов на вход

БФПО запрещается.

Ошибочные символы стирания с выхода двухпороговой схемы 17 записываются в матрицу памяти блока формирования полиномов ошибок БФПО.

Матрица памяти полиномов ошибок состоит из s строк и и столбцов. Следовательно, она содержит sn запоминающих ячеек, где и— длина кодовой комбинации, а s определяется по формуле:

4 (t< d — 1 максимальное число исправляемы . устройством ошибочных спмволсв в кодовой комбинации).

В регистр 22 из БФПО также параллельным кодом записывается первый полипом с одиночной ошибкой. 7 актовым импульсом Т, с частотой f>)sf;=(2 — 1)f> (где f> — скорость телеграфпрования), записанная кодовая комбинация из регистра 5 и полином ошибок из регистра 22 тактовым импульсом Ti считываются одновременно и подаются на входы сумматора 9, в котором производится исправление ошибочных символов. С выхода сумматора 9 кодовая комбинация с исправленным одним символом подается .на вход устройства

18 и записывается в регистр 11. При обнаружении ошибки на выходе устройства 18 появляется сигнал, который стирает комбинацию в регистре 11. В этом случае по цепи обратной связи считываемая комбинация из регистра 11 через ячейку 7 вновь записывается в регистр 5. Одновременно с этим из БФПО в регистр 22 записывается полипом с другой единичной ошибкой. Записанная комбинация из регистра 5 и полипом ошибок из регистра

22 -актовыми импульсами Т, считываются и подаются на входы сумматора 9.

С выхода сумматора кодовая комбинация с исправленным символом подается на входы устройства 18 и регистра l l. Если устройством И ошибка не обнаружена, то выход сумматора закрывается, принятая кодовая комбинация из регистра 11 переписывается в регистр lб и передается получателю.

При обнаружении ошибки устройством И принятая комбинация из регистра 11 стирается, и в этот регистр записывается комбинация с другими исправленными символами, записанными в регистр 22 из БФПО.

Таким образом БФПО записывается в регистр 22 s=2 — 1 всех возможных вариантов полиномов ошибок от однократных до 1-кратных включительно. Исправление прекр ащается в случае, если после исправления некоторого варианта устройством 18 ошибка не обнаружена. Если в результате исправления всех возможных вариантов из t ошибок устройство И ошибки обнаружены, то принятая кодовая комбинация стирается и по обратному каналу посылается сигнал «запрос» на повторную передачу.

Показанный на фиг. 2 БФПО рассчитан для исправления всех вариантов из t 3 ошибок в кодовой комбинации, длиной n=6.

Рассмотрим принцип работы БФПО. Предположим, что в принятой кодовой комбинации символы 1, 2 и 5 двухпороговой схемой 17 признаны ненадежными. В этом случае в регистр 28 в ячейки 1, 2 и 5 (на фиг. 2 за штриховяны) будут записаны «1». Тактовым импульсом Т,< эти ошибочные символы параллельным кодом переписываются в соответ"твующие ячейки буферного накопителя 24.

После этого с помощью распределителя 25 ошибочные символы записываются в матрицу

335689 памяти IM таким образом, .то в первых тре. строках записываются полпномы с однократными ошибками в 4-й, 5-й и 6-й строках — полиномы с двухкратными ошибками, наконец, в последней, 7-й строке полипом с трехкратной ошибкой (ячейки памяти, в которых записаны «1» заштрихованы). Запись «1» в указанном порядке обеспечивается ключевой схемой 26, состоящей из распределителя 27, триггеров 28 — 80 ячеек «ИЛИ» 81 — 85 и линии задержки 86 с использованием принципа совпадения токов.

В исходном положении с выхода триггера

28 на ячейки «ИЛИ» 82 — 85 подается высокое напряжение Е>. В результате во всех ячейках первого — седьмого рядов (строках) появляется подмагничивающий ток. При считывании распределителем 25 «единицы» из первой ячейки буферного накопителя 24 с ее выхода на все ячейки, расположенные в первом столбце матрицы памяти, подано высокое напряжение. Ячейки, на входы которых пода0о напряжение Е, под воздействием импульса с выхода первой ячейки накопителя 24 переходят в состояние «1».

С выхода первой ячейки буферного накопителя импульс напряжения подается также на вход схемы «ИЛИ» 81. Этот импульс через линию задержки 86 продвигает «1» в распределителе 27 из первой ячейки во вторую ячейку. Выходной импульс из первой ячейки распределителя 27 переводит триггер 28 в состояние, при котором высокое напряжение появляется на его незаштрихованном плече. Это напряжение переводит триггер 29 в положение, при котором на его незаштрихованном плече появляется высокое напряжение Е .

Это напряжение создает подмагничивающие токи во всех ячейках, расположенных во 2-й, 4-й, 6-й и 7-й строках матрицы памяти.

В дальнейшем распределителем 1 считывается «1» из 2-й ячейки буферного накопителя

24, появившееся высокое напряжение на выходе второй ячейки буферного накопителя 24 записывает «1» в ячейках, расположенных во

2-й, 4-й, 6-й и 7-й строках матрицы памяти.

Этот же импульс через схему «ИЛИ» 81 и линию задержки 86 переписывает «1» из 2-й ячейки распределителя 27 в 3-ю ячейку. В этом случае триггер 29 переходит в состояние, при котором на его незаштрихованном плече низкое напряжение, а триггер 80 — в положение, при котором на его незаштрихованном плече появляется высокое напряжение Ез.

Выходной импульс из 5-й ячейки и распределителя 25 считывает «1» из 5-й ячейки накопителя 24, который подаегся на входы всех ячеек матрицы памяти, расположенный в 5-ом столбце. Следовательно, во все ячейки этого столбца, расположенные в З-й, 5-й, 6-й и 7-й строках будут записаны «1».

Таким образом, в матрицу памяти оказались записанными все варианты полиномов ошибок, кратности 1 и менее (1<1<3).

В дальнейшем эти полиномы переписываются последовательно один за другим в регистр памяти 22. При считывании полинома ошибок из регистра 22 и принятой кодовой комбинации из регистра 5, в сумматоре 9 производится исправление тех символов, которые приняты как ошибочные (ненадежные).

Считывание полиномов ошибок из матрицы памяти производится распределителем 87 последовательно по строкам. Первым считывается полином, записанный в 1-й строке матрицы, затем во 2-й и т. д.

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

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

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

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

335689

Фиг.Z

Составитель В. Крылова

Техред T. Курилко

Редактор Л. Утехина

Корректор О, Тюрина

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

Заказ 1295 8 Изд. № 46б Тираж 448 Подписное

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

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