Патент ссср 255980

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ т.ВИДЕТЕПЬСТВУ

255980

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

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

Республик

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

Заявлено 08.Ч11.1968 (¹ 1254240/18-24) Кл. 21ат, 7/01 с присоединением заявки М

Приоритет

Опубликовано 04.Х1.1969. Бюллетень ¹ 34

Дата опубликования описан ия 4.Ч.1970

МП1 Н 04l

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

СССР

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

Г. Н. Устинов

Заявитель

УСТРОЙСТВО ДЛЯ ВОССТАНОВЛЕНИЯ СТИРАНИЙ

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

ПОСЛЕДОВАТЕЛЬНОСТИ

ГW — 1) е„е,")

Область .применения предлагаемого устройства — электросвязь, в частности — передача телекодовой информации по каналам связи.

Для двоичных циклических (и, к) -кодов

Боуза-Чоудхури известны устройства для восстановления стираний и исправления ошибок в двоичных стирающих каналах связи, обеспечивающие в соответствии с используемым (и, к)-кодом весом W восстановление е стираний и исправление 1 ошибок, если W) 21-,-е+ (.

Однако эти устройства не обеспечивают полного использования возможностей линейного (n, к) -кода восстанавливать стирания и исправлять ошибки в кодовой последовательности, так как не обеспечивают восстановления восстанавливаемой части сочетаний стираний кратности еь

W(e,(n — к, (Ж >2).

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

Во-вторых, при восстанавливаемости е стираний возможны случаи, когда число стертых единичных символов е и нулевых е"т символов в кодовой последовательносги довлегворяет неравенству

Г W — 11 где — целая часть, Тогда корректирую5 2 щая способность кода оказывается недостаточной для исправления ошибок в кодовой последовательности, возникающих в результате замены стертых симBî Iîâ символами 0 либо 1.

1о Так, например, если передавалась кодовая последовательность V=1100 1100 (используется (8, 4) — код), а из канала связи, принята последовательность V =1ХХОХ10Х, в которой стерты («Х» — символ стирания) два единич15 ны; и два нулевых символа, восстановить стирания таким устройством невозможно, ибо, как В первом цикле декодирования, так и Во втором, в кодовой последовательности образуюгся двухкратные ошибки, которые не могут

20 быть исправлены используемым (8. 4) — кодом.

Цель настоящего изобретения — обеспечение максимально возможной для данного (n, к)кода вероятности правильного приема кодовой

25 последовательности за счет полного использования возможностей линейного (n, к) -кода восстанавливать стирания и исправлять ошибК1f.

Если использовать только возможности ли30 нейных (n, к)-кодов восстанавливать стирания

255980 кратности e(W — 1, то кодом 8, 4 можно восстановить 37% сочетаний стираний, кодом

10, 5 — 17О/о, кодом 15, 5 — 30 /О. В то же время, если полностью использовать возможности кода восстанавливать стирания, эти цифры будут равны соответственно 59, 54 и 88 /О.

Комбинация стираний кратности е, считается восстанавливаемой, если е, столбцов проверочной матрицы Н линейного (n, к)-кода, каждый из .которых имеет номер, соответствующий номеру стертой |позиции в принятой кодовой последовательности, образу|от линей.но независимую подсистему системы столбцов проверочной матрицы Н.

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

Следовательно, если комбинация стираний невосстанавливаема, То среди е1 стертых позиций должно содержаться такое сочетание стертых позиций кратности j, W(j(e>, для которого значение проверочной комбинации (синдрома), вычисленное по последовательности с единичными символами только на стертых позициях, совпадает с нулевой комбинацией.

С целью более полного использования корректирующих возможностей циклических (n, к)-кодов, в предлагаемое устройство введена схема определения восстанавливаемости полученной комбинации стертых символов, входы которой соединены с выходами блока приема, а выходы в со входами блока управления и выдачи,,и блок восстановления части сочетаний стираний, который своими входами соединен с выходами схемы определения восстанавливаемости комбинации стираний и блока исправления ошибок, а выходами — со входами блока управления и выдачи.

С целью определения возможности восстановления стираний, схема определения восста ньвливаемости стираний полученной комбина ции стертых символов содержит блок определения числа стираний, соединенный входами с выходами блока приема, а выходами — co входами блока формирования контрольных комбинаций и блока управления. Блок формирования контрольных комбинаций связан входами с выходами блока приема и блока управления, а выходами — со входами блока управления. Блок вычисления проверочной комбинации и сравнения его с нулевой комбинацией соединен своими входами с выходами блока управления.

Функции схемы определения восстанавливаемости стиран ий,состоят в следующем.

В соответствии со стирающей последовательностью формируются различные и-разрядные контрольные последовательности, ксторые на позициях, подвергнутых стиранию, могут иметь символы О или 1, а на остальных позициях — только О. Минимальное число единичных символов в контрольной последовательности, необходимое для проверки восстанавливаемости стираний, равно W, а максималь5 ное n — к. Для каждой сформированной контрольной последовательности вычисляется значение проверочной комбинации (синдрома К), которое сравнивается с нулевой комбинацией. Если значечие синдрома К не сов10 падает с нулевой комбинацией ни для одной из контрольных последовательностей, комбинация стираний в принятой кодовой последовательности считается восстанавливаемой и дается разрешение на декодирование. В про15 тивном случае сочетание стираний считается невосстанавливаемым, и декодирование не проводится.

Если комбинация е стираний признана восстанавливаемой и выполняется неравенство

20 (1), корректирующая способность кода оказывается недостаточной для исправления ошибок, возникающих в результате замены стертых символов символами О или 1. Для восстановления таких комбинаций стираний в уст25 ройство вводят блок восстановления стираний, соединенный своими входами с выходами вычислителя синдрома кодовой последовательности и блока вычисления проверочной комбинации, а выходом — с регистром кодовой по30 следовательности. При этом увеличивается общее число контрольных последовательностей, под которыми в дальнейшем будем понимать и-разрядную комбинацию, которая на позициях, подвергнутых стиранию, может иметь

35 0 или 1, а на остальных позициях — только О.

Минимальное число единичных символов в контрольной последовательности должно быть на единицу больше t (t — корректирующая способность кода). а максимальное n — к.

40 Функции блока восстановления части стираний состоят в следующем..При числе стираний в кодовой последовагельности, равном е,, W(e,(n — к, значение проверочной комбинации, вычисленное для каждой контрольной по45 следовательности, наряду с .посту пленяем на сравнение с нулевой комбинацией, поступает и на сравнение со значением синдрома S, вычисленным для принятой кодовой последовательности, в которой стертые символы замене50 ны символами О. При совпадении проверочной комбинации со значением синдрома нулевые символы кодовой последовательности, находящиеся на позициях, номера которых совпадают с номерами позиций контрольной .последо55 вательности, на которых стоит символ 1, заменяются единичными.

Если в процессе перебора в=ех контрольных .последовательностей получено только одно совпадение проверочной последовательности с синдромом, кодовая последовательность, полученная в результате восстансвления, считается искомой и выдается получателю. Есди же совпадение не зафиксировано и при этом не было получено нулевое значение провероч65 ной комбинации, дастся разрешение на двух255980 эта77ное декодирование с исправлением кратны.; ошиоок.

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

Устройство содержиг блок 1 приема с фиксированием стертых позиций, состоящий из счетчика 2, подсчитывающего число стираний и вырабатывающего сигнал при числе стираний W=3,15-разрядного регистра 8 стирающей последовательности, 15-разрядного регистра 4 кодовой последовательности, схем

«ИЛИ» 5 — 8, схем «И» 9 — 11, схемы «НЕ» 12, схемы «С» 18 (сумматора по модулю 2); блок

14 исправления ошибок, включающий четырехразрядные регистры 15 и 16 с обратной связью для вычисления проверочной комбинации (15, 11)-кода, схему 17 сравнения синдрома 5 с комбинацией «0001», схему «ИЛИ» 18, схему «НЕ» 19, сумматор «С» 20; блок 21 управления и выдачи получателю декодпрованной информационной последовательности, состоящий из регистров 22, 28 первого и второго этапов декодирования, схемы 24 управления приемом и выработки тактовых импульсов Г ь схемы 25 управления декодированием и выработки тактовых импульсов Т, схемы 26 упразления выводом кодовой последсвательпости пз регистров и выработки тактовых импульсов

Т", схем «ИЛИ» 27 — 29, схем «И» 80 — 89, триггеров 40 и 41; блок 42 определения числа стираний, состоящий из счетчика 48 íà (n— — к+ 1), схемы 44 сравнения показаний счетчика со значением W=3 и схемы 45 сравнения показаний счетчика со значением и†" — 4; блок 46 формирования контрольных комбинаций; блок 47 вычисления проверочной комбинации (синдрома К) и сравнения ее с комбинацией «0000», включающий четырехразрядный регистр 48 для вычисления синдрома К, схему 49 сравнения показаний регистра 48 с комбинацией «0000» и схему «ИЛИ» 50; блок восстановления 51, состоящий из 15-разрядного регистра 52 для хранения контрольной последовательности, схемы 58 сравнения проверочной комбинации (синдрома К) с синдромом Ь, вычисленным в регистре 15, схемы «ИЛИ» 54 и схемы «И» 55; блок 56 управления, включающий схему 57 выработки тактовых Т", и управляющих импульсов; схемы «ИЛИ» 58 и 59, схемы «И» 60 — 68, схемы «НЕ» 64 и 65.

Рассмотрим работу устройства восстановления стираний и исправления ошибок.

Режим приема. Блок приема 1 принимает кодовую последовательность из канала связи, одновременно заменяя стертые символы символам и «О», и записывает ее в регистры 4 и 15 через схемы «ИЛИ» 7и«С»18, В это же время блок 1 формирует стирающую последовательность путем занесения в регистр 8 символа

«1» .на позиции, подвергнутые стиранию. Параллельно стирающая последовательность поступает на регистр 48 для вычисления проверочной комбинации (синдрома К). Регистр 48 выполнен аналогично регистрам 15 и 16. После 15 тактов с начала поступления кодовой

27

65 последовательности в регистрах 15 и 48 оказывается записанной проверочная комбинация (15, 11) -кода Боуза-Чоудхури.

С окончанием режима приема схема 24 управления приемом вырабатываег сигнал, поступающий на схемы «И» 10 и 11 для определения числа стираний, При числе стираний

eI = W 1 =2 сигнал со схемы 24 через схемы

«И» 11 и «ИЛИ» 8 поступает на схему 25 управления декодированием, которая в случае отсутствия стираний проводит один цпк.7 декодирования, а при наличии стираний— два цикла декодирования.

При числе стираний ei) 1Г=З сигнал со схемы 24 через схему «И» 10 поступает на схему определения восстанавливаемости стираHHlI H BoccTBHoD,7e HHII части сочетаний ci ираний крат|ости t+1(eI и е,(п — к, где t=1— кр атнос fb исправляемых (15, 11) -кодом ошибок (см. фиг. 2).

Режим декодирования. С поступлением сигнала на схему 25 управления декодированием она вырабатывает управляющие сигналы: Ц,, подключающий вход регистра 22, Уь переписывающий содержимое регистра 15 в регистр 16, и тактовые импульсы Ть

В регистрах 8 и 4 с поступлением тактовых импульсов Т1 происходит циклический сдвиг содержи»oro, Кодовая последовательность из регистра 4 поступает Ii регистр 22 через сумматор «С» 20 одновременно с вводом в регистры 4 и 15 результата суммирования кодовой последовательности со стирающей последовательностью (нулевые символы на стертых позициях заменяются символами «1»). В регистре 15 при этом образуются элементы матрицы М (15, 11)-кода Боуза-Чоудхури, следующие .после записанного в него элемента. Блок сравнения срабатывает и выдает импульс в сумматор «С» 20 в тот момент, когда в ре гистр 16 поступает элемент матрицы (Р, соответствующий комоинацип ZIP=0001. В этот же момент с выхода регистра 8 в сумматор

«С» 20 поступает разряд, подлежащий исправлению. С окончанием записи кодовой IIoследовательности в регистр 22 очищается регистр 16 (управляющим сигналом У ) и при наличии стираний организуется второй цикл де одированпя, т. е. вырабатывается управляющий сигнал Ц, вырабатывается сигнал У,, переписывающий B регистр 16,проверочную комбинацию (полученную в схеме 44), и ко70вая последовательность переписывается из регистра 4 через сумматор «С»20 в регистр 28.

С окончанием второго цикла декодирования схема 26 выдает получателю одну из находящихся в регистрах 22 и 28 кодовых последовательностей, отличающуюся от полученной кодовой последовательности íà t или меньшее число нестертых разрядов (д.7я (15, 11)-кода

i =1). Это обеспечивается схемами «И» 88 и 89 и триггером 41.

При отсутствии стираний проводится один цикл декодирования, и блок 21 управления выдает получателю кодовую последователь255980 ность из регистра 22 при помощи триггеров

40, 41 и схем «И» 88 и 84.

Режим определения в ос стан а вливаем ости сочетаний стираний.

Как было оговорено выше, при числе стираний е ) Й7=3 (для (15, 11)-кода) сигнал со схемы 24 через схему «И» 10 поступает на схему (см. фиг. 3) определения восстанавливаемости стираний и восстановления части сочетаний стираний кратности 2(е,(4. К этому моменту в регистре 48 уже содержится значение проверочной комбинации (синдрома К1, вычисленное для стирающей последовательности. Сигналом lg опрашиваются схемы сравнения 44 и 45.

При числе стираний е,=3 схема сравнения 44 вырабатывает сигнал, опрашивающий схему сравнения 49 через схему «ИЛИ» 50, Если значение синдрома в регистре 48 не совпадает с нулевой комбинацией, то сигнал ь через схемы «И» 61, «ИЛИ» 58, «И» 68 проходит на схему 25 управления декодированием (см. фиг. 1) и организуется режим декодирования кодовой последовательности. Если значение синдрома К в регистре 48 совпадает с нулевой комбинацией, это свидетельствует о невосстанавливаемости комбинации стираний, происшедших в кодовой .последовательности. Сигнал i2 со схемы сравнения 49 .приводит устройство восстановления в исходное состояние и выдается сигнал В (см. фиг.1), свидетельствующий о том, что кодовая по.ледовательность содержит невосстанавливаемую комбинацию стертых символов.

При числе стираний е — — 4 наряду с невосстанавливаемыми комбинациями стертых символов в кодовой последовательности возможны стирания, которые могут быть исправлены используемым кодом. В соответствии с этим при числе стираний е,=4 (срабатыьает схема сравнения 45) при .помощи блоков 46, 47, 51 и 56 формируются всевозможные контрольные последовательности и для каждой из них вычисляется проверочная комбинация, которая сравнивается с нулевой комбинацией и со значением синдрома, полученным в регистре 15.

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

Сигнал со схемы сравнения 45 поступает на схему 57 выработки тактовых Т", и управляющих импульсов и на блок 46 формирования контрольных комбинаций.

В регистре P-1 блока 46 (см. фиг, 3) в исходном состоянии записана комбинация «0011» для обеспечения формирования всех одиннадцати контрольных последовательностей с двумя, тремя и четырьмя единичными символами, 8 а в регистре Р-2 — комбинация «1000». Содержимое регистра Р-2 сдвигается вправо сигналами со схем «И» 66 — 69 через схему «ИЛИ» 70, а в регистре P-1 — сигналом с регистра P-2.

С поступлением тактовых импульсов T" > на регистр 8 происходит циклический сдвиг его содержимого с одновременным поступлением последовательности на схему «И» 71 (см. фиг. 3) и далее — через схемы «И» 66, 69, 72 щ и 75 в регистры 48 и 52 (см. фиг. 2). Блок 46 преобразует поступающую на его вход стирающую последовательность в очередную контрольную последовательность в соответствии с комбинацией, записанной в регистре P-1, и

15 подает ее в регистры 48 и 52.

Рассмотрим формирование первой контрольной последовательности в случае, когда стирающая последовательность 1 „имеет вид

001010001100000.

20 На шестом такте T" > срабатывает схема

«И» 66, происходит сдвиг на один разряд вправо в регистре P-2, а схема «И» 72 сигнала не выдает, так как в соответствующем разряде регистра Р-1 содержится «О». Следовательно, 25 на шестом такте в регистры 48 и 52 поступает символ «О». Аналогичные действия .происходят и на седьмом такте, срабатывает схема

«И» 67, На 11-м такте срабатывают схемы «И» 68 зО и 74, в регистре P-2 единица сдвигается в последний разряд, и в регистры 48 и 52 поступает символ «1».

На 13-м такте срабатывают схемы «И» 69 и 75, содержимое регистра P-2 восстанавливается в первоначальном положении, содержимое регистра P-1 сдвигается на один разряд вправо (0110), в регистры 48 и 52 поступают,символы «1». После 15 тактов,в регистре 52 оказывается записанной контрольная

4р последовательность V 001010000000000, а в регистре 48 — проверочная комбинация, вычисленная в соответствии с контрольной последовательностью Vy. После 15 тактов схема управления вырабатывает сигнал, поступающий на опрос схем управления 74 и 76. После этого вновь вырабатываются 15 тактовых импульсов и начинается формирование второй контрольной, последовательности. Формирование прекращается при появлении в регистре

gp P-1 комбинации «0001», При этом срабатывает схема «И» 76, восстанавливается первоначальное содержимое регистра P-1 (во второй разряд записывается «1») и сигнал подается на схему 57 (прекращается выработка тактовых импульсов), а также на схемы «И» 62 и 68.

Если вычисленная проверочная комбинация г. регистре 48 совпадает с нулевой комбинацией, что свидетельствует о невосстанавливаемости комбинации стираний в кодовой последовательности, схема сравнения 49 вырабатывает сигнал j2, прекращающий декодирование.

Если проверочная комбинация в регистре 48, вычисленная .для одной из контрольных последовательностей V, совпадает со значением

255980

10 синдрома, вычисленным в регистре 15 (см. фиг. 2), блок восстановления 51 вырабатывает управляющий сигнал на схемы «И» 55, 60 и 62.

Тогда во время очередного цикла формирования очередной контрольной последовательности тактовые импульсы Т" ь поступающие на регистры 4 (через схему «ИЛИ» 1), 22 (через схему «ИЛИ» 27) и 52, в регистр 22 записывается последовательность, представляющая собой сумму по модулю 2 (образуется в сумматоре «С» 20) принятой кодовой,последовательности и контрольной последовательности V,.

Таким образом, в процессе проверки восстанавливаемости стираний возможны три случая: а) одна из проверочных комбинаций Е (синдром К, ) совпадает с нулевой комбинацией; б) одна из проверочных комбинаций (синдром К ) совпадает со значением синдрома $, в то время как ни одна другая проверочная комбинация не совпадает с нулевой комбинацией; в),ни одна проверочная комбинация не совпадает ни с нулевой комбинацией, ни со значением синдрома S, что свидетельствует о том, что из четырех стираний в кодовой последовательности произошло стирание только одного единичного символа.

В соответствии с этим при окончании процесса формирования контрольных последовательностей сигнал 1 о со схемы «И» 76 (см, фиг. 3),проходит через схему «И» 62, если имеет место второй случай, или через схему

«И» 68, если имеет место третий случай.

Сигнал /4 со схемы «И» 62 запускает схему управления и выработки тактовых импульсов

Т", 26, которая обеспечивает выдачу,получателю восстановленной кодовой последовательности, записанной в регистре 21.

Сигнал 1з со схемы «И» 68 поступает на за.пуск схемы 25 управления .декодированием, которая выполняет следующие действия, связанные с декодированием .кодовой последовательности, и по окончании декодирования передает управление схеме управления 26, которая при |помощи схем «И» 84 и 89 и триггеров

40 и 41 обеспечивает выдачу получателю восстановленной кодовой последовательности.

При числе стираний е,)и — к счетчик 48 (блок 42) вырабатывает сигнал 1., свидетельствующий о приеме кодовой последовательности с невосстанавливаемой комбинацией стер5 тых символов.

Предлагаемое устройство обеспечивает восстановление максимально возможного числа стираний кратности 3 и 4, т. е. из 455 сочетаний стираний кратности 3 оно восстанавлиlo вает 420, а из 1365 сочетаний стираний кратности 4 восстанавливает 855.

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

1. Устройство для восстановления стираний и исправления ошибок в кодовой последовательности, содержащее блок:приема с фиксированием стертых позиций, блок исправления ошибок, блок управления и выдачи декодиро20 ванной информационной последовательности, отличающееся тем, что, с целью более полного использования корректирующих возможностей циклических (и, к)-кодов, в него введены схема определения восстанавливаемости полу25 ченной комбинации стертых символов, которая своими входами соединена с выходами блока приема, а выходамп — со входами блока управления и выдачи, и блок восстановления части сочетаний стираний, который своими

50 входами соединен с выходами схемы определения восстанавливаемости комбинации стираний и блока исправления ошибок, а выходами — со входами блока управления и выдачи.

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

40 входами с выходами блока приема, а выходами — со входами блока формирования контрольных комбинаций и блока управления, блок формирования контрольных комбинаций, связанный своими входами с выходами

45 блока приема и блока управления, а выходами в со входами блока управления, блок вычисления проверочной комбинации и сравнения ее с нупевой комбинацией, соединенный своими входами с выходами блока управле50 ния, и блок управления.

<о !

9 ив 3

Составитель Л. А. Горская

Редактор Б. Б. Федотов Техред Л. В. Куклина Корректоры: О. Б. Тюрина и О. И. Усова

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

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

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

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