Устройство для исправления ошибок в кодовой комбинации
Иллюстрации
Показать всеРеферат
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