255980

О П И С А Н И Е 255980ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Согоа Советских Социалистических РеспубликЗависимое от авт. свидетельст влено 08.ЧН,1968 (М 1254240/18 К ч 21 ат 7/О присоединением заявки Ло ПриоритетОпубликовано 04.Х 1,1969. БюллеДата опубликования описания 4 МП 1 Н 041ДК 621 394 14(088 8 Комитет по делам обретений и открытийАвторизобретени Н, Устинов аявител СТАНОВЛЕНИЯ СТИРАНОШИБОК В КОДОВОЯВАТЕЛ ЬНОСТИ СТ ИСТ ВО ДЛЯ В ИСПРАВЛЕНИПОСЛЕД е,") ивгде2 чая часть, Тогда корректируюОбласть применения предлагаемого устройства - электросвязь, в частности - передачателекодовой информации по каналам связи,Для двоичных циклических (и, к) -кодовБоуза-Чоудхури известны устройства для восстановления стираний и исправления ошибокв двоичных стирающих каналах связи, обеспечивающие в соответствии с используемым(и, к)-кодом весом Ю восстановление е стираний и исправление 1 ошибок, если 1 Р)25+е+1, 10Однако эти устройства не обеспечиваютполного использования возможностей линейного (и, к) -кода восстанавливать стирания иисправлять ошибки в кодовой последовательности, так как не обеспечивают восстановления восстанавливаемой части сочетаний стираний кратности еУ(е,(и - к, (Ю")2).Это происходит вследствие того, что, во-первых, при числе стираний, кратном е нарядус восстанавливаемыми сочетаниями стираниймогут быть и невосстанавливаемые, что создает неопределенность, которая не можетбыть разрешена с помощью этих устройств. 25Во-вторых, при восстанавливаемости е, стираний возможны случаи, когда число стертыхединичных символов е, и нулевых е"т символов в кодовой последовательносги довлегворяет неравенству ЗО щая способность кода оказывается недостаточной для исправления ошибок в кодовой последовательности, возникающих в результате замены стертых символов символами 0 либо 1.Так, например, если передавалась кодовая последовательность Г= 1100 1100 используется (8, 4) - код, а из канала связи ,принята последовательность Р=1 ХХОХ 10 Х, в которой стерты (Х - символ стирания) два единичных и два нулевых символа, восстановить стирания таким устройством невозможно, ибо, как В перВом цикле декодироВания, так и Во втором, в кодовои последовательности образуюгся двухкратные ошибки, которые не могут быть исправлены используемым (8, 4) - кодом.Цель настоящего изобретения - обеспечение максимально возможной для данного (и, к)- кода вероятности правильного приема кодовой последовательности за счет полного использования возможностей линейного (и, к) -кода восстанавливать стирания и исправлять ошибкгг.Если использовать только возможности линейных (и, к)-кодов восстанавливать стираниякратности е(У - 1, то кодом 8, 4 можно восстановить 37 сочетаний стираний, кодом 10, 5 - 17 о , кодом 15, 5 - 30 о , В то же время, если полностью использовать возможности кода восстанавливать стирания, эти цифры будут равны соответственно 59, 54 и 88 О 1 О.Комбинация стираний кратности е, считается восстанавливаемой, если е, столбцов проверочной матрицы Н линейного (а, к)-кода, каждый из которых имеет номер, соответствующий номеру стертой позиции в принятой кодовой последовательности, образуот линейно независимую подсистему системы столбцов проверочной матрицы Н.Только в этом случае значение проверочной комбинации, полученной в результате умножения транспонированной матрицы Н на вектор с единичной компонентой на стертых позициях, соответствуют лишь одному сочетанию вектор-столбцов матрицы Н, номера которых соответствуют номерам стертых позиций,Следовательно, если комбинация стиран гй невосстанавливаема, то среди е, стертых позиций должно содержаться такое сочетание стертых позиций кратности 1, У(1(е для которого значение проверочной комбинации (синдрома), вычисленное по последовательности с единичными символами только на стертых позициях, совпадает с нулевой комбинацией.С целью более полного использования корректирующих возможностей циклических (а, к)-кодов, в предлагаемое устройство введена схема определения восстанавливаемости полученной комбинации стертых символов, входы которой соединены с выходами блока приема, а выходы в со входами блока управления и выдачии блок восстановления части сочетаний стираний, который своими входами соединен с выходами схемы определения восстанавливаемости комбинации стираний и блока исправления ошибок, а выходами - со входами блока управления и выдачи.С целью определения возможности восстановления стираний, схема определения восста навливаемссти стираний полученной комбинации стертых символов содержит блок определения числа стираний, соединенный входами с выходами блока приема, а выходами - со входами блока формирования контрольных комбинаций и блока управления. Блок формирования контрольных комбинаций связан вхо. дами с выходами блока приема и блока управления, а выходами - со входами блока управления, Блок вычисления проверочной комбинации и сравнения его с нулевой комбинацией соединен своими входами с выходами блока управления.Функции схемы определения восстанавливаемости стираний,состоят в следующем, В соответствии со стирающей последовательностью формируются различные а-разрядные контрольные последовательности, ксторые на позициях, подвергнутых стиранию, могут иметь символы О или 1, а на остальных позициях - только О. Минимальное число единичных символов в контрольной последовательности, необходимое для проверки восстанавливаемости стираний, равно К, а максималь ное и - к, Для каждой сформированной контрольной последовательности вычисляется значение проверочной комбинации (синдрома К), которое сравнивается с нулевой комбинацией, Если значечие синдрома К не сов падает с нулевой комбинацией ни для однойиз контрольных последовательностей, комбинация стираний в принятой кодовой последовательности считается восстанавливаемой и дается разрешение на декодирование. В про тинном случае сочетание стираний считаетсяневосстанавливаемым, и декодирование не проводится.Если комбинация е 1 стираний признана восстанавливаемой и выполняется неравенство 20 (1), корректирующая способность кода оказывается недостаточной для исправления ошибок, возникающих в результате замены стертых символов символами О или 1. Для восстановления таких комбинаций стираний в уст ройство вводят блок восстановления стираний,соединенный своими входами с выходами вычислителя синдрома кодовой последовательности и блока вычисления проверочной комбинации, а выходом - с регистром кодовой по следовательности. При этом увеличивается общее число контрольных последовательностей, под которыми в дальнейшем будем понимать и-разрядную комбинацию, которая на позициях, подвергнутых стиранию, может иметь 35 О или 1, а на остальных позициях - только О,Минимальное число единичных символов в контрольной последовательности должно быть на единицу больше 1 (1 в корректирующая способность кода), а максимальное л - к.40 Функции блока восстановления части стираний состоят в следующем. При числе стираний в кодовой последовагельности, равном е У(е,(п - к, значение проверочной комбинации, вычисленное для каждой контрольной по следовательнссти, наряду с поступлением насравнение с нулевой комбинацией, поступает и на сравнение со значением синдрома 5, вычисленным для принятой кодовой последовательности, в которой стертые символы замене ны символами О. При совпадении проверочнойкомбинации со значением синдрома нулевые символы кодовой последовательности, находящиеся на позициях, номера которых совпадают с номерами позиций контрольной последовательности, на которых стоит символ 1, заменяются единичными.Если в процессе перебора в:ех контрольныхпоследовательностей получено только одно совпадение проверочной последовательности с синдромом, кодовая последовательность, полученная в результате восстансвления, считается искомой и выдается получателю. Если же совпадение не зафиксировано и при этом не было получено нулевое значение провероч ной комбинации, дастся разрешение на двухэтапное декодирование с исправлением кратных ошиоок.На фит. 1, 2 и 3 изображена принципиально- логическая схема устройства,Устройство содержиг блок 1 приема с фиксированием стертых позиций, состоящий из счетчика 2, подсчитывающего число стираний и вырабатывающего сигнал при числе стираний Р=3,15-разрядного регистра 3 стирающей последовательности, 15-разрядного регистра 4 кодовой последовательности, схем ИЛИ 5 - 8, схем И 9 - 11, схемы НЕ 12, схемы С 13 (сумматора по модулю 2); блок 14 исправления ошибок, включающий четырех- разрядные регистры 15 и 16 с обратной связью для вычисления проверочной комбинации (15, 11)-кода, схему 17 сравнения синдрома 5 с комбинацией 0001, схему ИЛИ 18, схему НЕ 19, сумматор С 20; блок 21 управления и выдачи получателю декодцрованной информационной последовательности, состоящий из регистров 22, 23 первого и второго этапов декодирования, схемы 24 управления приемом и выработки тактовых импульсов Ть схемы 25 управления декодированием ц выработки тактовых импульсов Т, схемы 26 упразления выводом кодовой цоследсвательпостц цз регистров и выработки тактовых импульсов Т"схем ИЛИ 27 - 29, схем И ЗО - 39, триггеров 40 и 41; блок 42 определения числа стираний, состоящий из счетчика 43 на (ив - к+ 1), схемы 44 сравнения показаний счетчика со значением Ж=3 и схемы 45 сравнения показаний счетчика со значением и - к - 4; блок 46 формиоования контрольных комбинаций; блок 47 вычисленця проверочной комбинации (синдрома К) и сравнения ее с комбинацией 0000, включающий четырехразрядный регистр 48 для вычисления синдрома К, схему 49 сравнения показаний регистра 48 с комбинацией 0000 и схему ИЛИ 50; блок восстановления 51, состоящий из 15-разрядного регистра 52 для хранения контрольной последовательности, схемы 53 сравнения проверочной комбинации (синдрома 1 с синдромом Ь, вычисленным в регистре 15, схемы ИЛИ 54 и схемы И 55; блок 56 управления, включающий схему 57 выработки тактовых Т", и управляющих импульсов; схемы ИЛИ 58 и 59, схемы И 60 - 63, схемы НЕ 64 и 65.Рассмотрим работу устройства восстановления стираний и исправления ошибок.Режим приема. Блок приема 1 принимает кодовую последовательность из канала связи, одновременно заменяя стертые символы символами О, и записывает ее в регистры 4 и 15 через схемы ИЛИ 7 иС 13, В это же время блок 1 формирует стирающую последовательность путем занесения в регистр 3 символа 1 на позиции, подвергнутые стиранию. Г 1 араллельно стирающая последовательность поступает на регистр 48 для вычисления проверочной комбинации (синдрома К). Регистр 48 выполнен аналогично регистрам 15 и 16. После 15 тактов с начала поступления кодовой 5 10 15 2 з 25 30 35 40 45 50 55 60 65 последовательности в регистрах 15 и 48 оказывается записанной проверочная комбинация (15, 11)-кода Боуза-Чоудхури.С окончанием режима приема схема 24 управления приемом вырабатываег сигнал, поступающий на схемы И 10 ц 11 для определения числа стираний, Прц числе стираний е, = 117 в =2 сигнал со схемы 24 через схемы И 11 ц ИЛИ 8 поступает на схему 25 управления декодированием, которая в случае отсутствия стираний проводит один цикл декодирования, а при наличии стираний - два цикла декодирования.Прц числе стираний е,) 117=3 сигнал со схемы 24 через схему И 10 поступает на схему определения восстанавлцваемостц стираний и восстановления части сочетаний сгиранцй кратности 1+1(е, ц е,(п - к, где =1 - кратносгь исправляемы.; (15, 11)-кодом ошибок (см. фиг. 2),Режим декодирования. С поступлением сигнала на схему 25 управления декодированием она вырабатывает управляющие сигналы: Ц подключающий вход регистра 22, Уь переписывающий содержимое регистра 15 в регистр 16, ц тактовые импульсы ТьВ регистрах 3 ц 4 с поступлением тактовых импульсов Т, происходит циклический сдвиг содержимого, Кодовая последовательность из регистра 4 поступает в регистр 22 через сумматор С 20 одновременно с вводом в регистры 4 ц 15 результата суммирования кодовой последовательности со стирающей последовательностью (нулевые символы на стертых позициях заменяются символами 1), В регистре 15 прц этом образуются элементы матрц. цы М" (15, 11)-кода Боуза-Чоудхури, следующие после записанного в него элемента. Блок сравнения срабатывает ц выдает импульс в сумматор С 20 в тот момент, когда в ре гцстр 16 поступает элемент матрицы Мф, соответствующий комоинацип 71=0001. В этот же момент с выхода регистра 3 в сумматор С 20 поступает разряд, подлежащий исправлению. С окончанием записи кодовой последовательности в регистр 22 очищается регистр 16 (управляющим сигналом У,) ц прц наличии стираний организуется второй цикл декодирования, т. е. вырабатывается управляющий сигнал Ц, вырабатывается сигнал У переписывающий в регистр 16,проверочную комбинацию (полученную в схеме 44), ц кодовая последовательность переписывается из регистра 4 через сумматор С 20 в регистр 23.С окончанием второго цикла декодирования схема 26 выдает получателю одну из находящихся в регистрах 22 и 23 кодовых последовательностей, отличающуюся от полученной кодовой последовательности на 1 или меньшее число нестертых разрядов для (15, 11)-кода 1= Ц. Это обеспечивается схемами И ЗЗ и 39 и триггером 41.При отсутствии стираний проводится один цикл декодирования, и блок 21 управления выдает получателю кодовую последовательность из регистра 22 при помощи триггеров 40, 41 и схем И 88 и 84.Режим определения в ос стан а вливаемм ости сочетаний стираний.Как было оговорено выше, при числе стираний е,)К=З для (15, 11)-кода сигнал со схемы 24 через схему И 10 поступает на схему (см. фиг. 3) определения восстанавливаемости стираний и восстановления части сочетаний стираний кратности 2(е,(4. К этому моменту в регистре 48 уже содержится значение проверочной комбинации (синдрома К 1, вычисленное для стирающей последовательности. Сигналомопрашиваются схемы сравнения 44 и 45.При числе стираний е, =3 схема сравнения 44 вырабатывает сигнал, опрашивающий схему сравнения 49 через схему ИЛИ 50,Если значение синдрома в регистре 48 не совпадает с нулевой комбинацией, то сигнал ь через схемы И 61, ИЛИ 58, И 63 проходит на схему 25 управления декодированием (см. фиг, 1) и организуется рен(им декодирования кодовой последовательности. Если значение синдрома К в регистре 48 совпадает с нулевой комбинацией, это свидетельствует о невосстанавливаемости комбинации стираний, происшедших в кодовой последовательности. Сигналсо схемы сравнения 49 приводит устройство восстановления в исходное состояние и выдается сигнал В (см. фиг.1), свидетельствующий о том, что кодовая последовательность содержит невосстанавливаемую комбинацию стертых символов.При числе стираний е,=4 наряду с невосстанавливаемыми комбинациями стертых символов в кодовой последовательности возможны стирания, которые могут быть исправлены используемым кодом. В соответствии с этим при числе стираний е,=4 (срабатыьает схема сравнения 45) при помощи блоков 46, 47, 51 и 56 формируются всевозможные контрольные последовательности и для каждой из них вычисляется проверочная комбинация, которая сравнивается с нулевой комбинацией и со значением синдрома, полученным в регистре 15.При совпадении проверочной комбинации со значением синдрома, полученным в регистре 15, и отсутствии совпадений вычисленных проверочных комбинаций с нулевой комбинацией получателю в качестве искомой выдается кодовая последовательность, полученная в результате суммирования по модулю 2 принятой кодовой последовательности с контрольной, для которой проверочная комбинация совпала с синдромом.Сигнал со схемы сравнения 45 поступает на схему 57 выработки тактовых Т", и управляющих импульсов и на блок 46 формирования контрольных комбинаций.В регистре Рблока 46 (см. фиг, 3) в исходном состоянии записана комбинация 0011 для обеспечения формирования всех одиннадцати контрольных последовательностей с дву- мя, тремя и четырьмя единичными символами,8а в регистре Р- комбинация 1000. Содер.жимое регистра Рсдвигается вправо сигнала.ми со схем И бб - 69 через схему ИЛИ 70,а в регистре Р- сигналом с регистра Р.С поступлением тактовых импульсов Т", нарегистр 8 происходит циклический сдвиг егосодержимого с одновременным поступлениемпоследовательности на схему И 71 (см.фиг. 3) и далее - через схемы И бб, 69, 721 О и 75 в регистры 48 и 52 (см. фиг. 2). Блок 46преобразует поступающую на его вход стирающую последовательность в очередную контрольную последовательность в соответствиис комбинацией, записанной в регистре Р, и15 подает ее в регистры 48 и 52.Рассмотрим формирование первой контрольной последовательности в случае, когдастирающая последовательность 1 имеет вид001010001100000.20 На шестом такте Т" срабатывает схемаИ 66, происходит сдвиг на один разрядвправо в регистре Р, а схема И 72 сигналане выдает, так как в соответствующем разрядерегистра Рсодержится О, Следовательно,25 на шестом такте в регистры 48 и 52 поступаетсимвол О, Аналогичные действия;происходят и на седьмом такте, срабатывает схемаИ 67,На 11-м такте срабатывают схемы И 68зО и 74, в регистре Рединица сдвигается в последний разряд, и в регистры 48 и 52 поступает символ 1.На 13-м такте срабатывают схемы И 69и 75, содержимое регистра Рвосстанавливается в первоначальном положении, содержимое регистра Рсдвигается на один разряд вправо (0110), в регистры 48 и 52 поступают,символы 1. После 15 тактов,в регистре 52 оказывается записанной контрольная4 О последовательность Г, 001010000000000, а врегистре 48 в проверочная комбинация, вычисленная в соответствии с контрольной последовательностью Р. После 15 тактов схемауправления вырабатывает сигнал, поступающпй на опрос схем управления 74 и 76. Послеэтого вновь вырабатываются 15 тактовых импульсов и начинается формирование второйконтрольной, последовательности. Формирование прекращается при появлении в регистре0 Ркомбинации 0001, При этом срабатываетсхема И 76, восстанавливается первоначальное содержимое регистра Р(во второй разряд записывается 1) и сигнал подается насхему 57 (прекращается выработка тактовыху импульсов), а также на схемы И 62 и 63.Если вычисленная проверочная комбинацияг. регистре 48 совпадает с нулевой комбинацией, что свидетельствует о невосстанавливаемости комбинации стираний в кодовой последовательности, схема сравнения 49 вырабатывает сигнал 1 р, прекращающий декодирование.Если проверочная комбинация в регистре 48, вычисленная для одной из контрольных последовательностей 1, совпадает со значением255980 10 синдрома, вычисленным в регистре 15 (см. фиг. 2), блок восстановления 51 вырабатывает управляющий сигнал на схемы И 55, 60 и 62. Тогда во время очередного цикла формирования очередной контрольной последовательности тактовые импульсы Т" поступающие на регистры 4 (через схему ИЛИ 1), 22 (через схему ИЛИ 27) и 52, в регистр 22 записы. вается последовательность, представляющая собой сумму по модулю 2 (образуется в сумматоре С 20) принятой кодовой,последовательности и контрольной последовательности У;. Таким образом, в процессе проверки восстанавливаемости стираний возможны три случая:а) одна из проверочных комбинаций , (синдром К, ) совпадает с нулевой комбинацией;б) одна из проверочных комбинаций Е, (синдром К,) совпадает со значением синдрома 5, в то время как ни одна другая проверочная комбинация не совпадает с нулевой комбинацией;в),ни одна проверочная комбинация не совпадает ни с нулевой комбинацией, ни со значением синдрома 5, что свидетельствует о том, что из четырех стираний в кодовой последовательности произошло стирание только одного единичного символа.В соответствии с этим при окончании процесса формирования контрольных последовательностей сигнал 1; со схемы И 76 (см, фиг. 3),проходит через схему И 62, если имеет место второй случай, или через схему И 63, если имеет место третий случай.Сигнал 14 со схемы И 62 запускает схему управления и выработки тактовых импульсов Т", 26, которая обеспечивает выдачу,получателю восстановленной кодовой последовательности, записанной в регистре 21.Сигнал р со схемы И 63 поступает на запуск схемы 25 управления .декодированием, которая выполняет следующие действия, связанные с декодированием .кодовой последовательности, и по окончании декодирования передает управление схеме управления 26, которая при помощи схем И 34 и 39 и триггеров 40 и 41 обеспечивает выдачу получателю восстановленной кодовой последовательности. При числе стираний е,)п - к счетчик 43(блок 42) вырабатывает сигнал 1., свидетельствующий о приеме кодовои последовательности с невосстанавливаемой комбинацией стер тых символов.Предлагаемое устройство обеспечивает восстановление максимально возможного числа стираний кратности 3 и 4, т. е. из 455 сочетаний стираний кратности 3 оно восстанавли вает 420, а из 1365 сочетаний стираний кратности 4 восстанавливает 855. Предмет изобретения 15 1. Устройство для восстановления стиранийи исправления ошибок в кодовой последовательности, содержащее блок:приема с фиксированием стертых позиций, блок исправления ошибок, блок управления и выдачи декодиро ванной информационной последовательности,отличающееся тем, что, с целью более полного использования корректирующих возможностей циклических (и, к)-кодов, в него введены схема определения восстанавливаемости полу ченной комбинации стертых символов, котораясвоими входами соединена с выходами блока приема, а выходамп - со входами блока управления и выдачи, и блок восстановления части сочетаний стираний, который своими 30 входами соединен с выходами схемы определения восстанавливаемости комбинации стираний и блока исправления ошибок, а выходами - со входами блока управления и выдачи.2. Устройство по п. 1, отличающееся тем, что, 35 с целью определения возможности восстановления стираний, схема определения восстанавливаемости стираний полученной комбинации стертых символов содержит блок определения числа стираний, соединенный своими 40 входами с выходами блока приема, а выходами - со входами блока формирования контрольных комбинаций и блока управления, блок формирования контрольных комбинаций, связанный своими входами с выходами 45 блока приема и блока управления, а выходами - со входами блока управления, блок вычисления проверочной комбинации и сравнения ее с ну.певой комбинацией, соединенный своими входами с выходами блока управле ния, и блок управления, 255980255980 иВ оставитель Л, А. ГорскаяТехред Л, В. Куклина актор Б. Б. Федот Подписное тий при Совете Министров СССР наб д. 4/5 ография, пр. Сапунова, 2 Заказ 1172/2 Тираж 4ЦНИИПИ Комитета по делам изобретений и оМосква Ж, Раушск орректорьк О. Б. Тюрина и О. И. Усова