Устройство декодирования каскадного кода рида-соломона

Устройство декодирования каскадного кода рида-соломона

Реферат

 

Устройство содержит буферный регистр данных, вычислитель синдромов, блок управления и синхронизации, первый и второй счетчики символов кодового слова, счетчик флагов стирания, генератор локаторов, схему управления записью номеров стертых символов и их локаторов, дешифратор количества флагов, регистровый файл номеров стертых символов, первый и второй блоки принятия решений, блок стираний, блок обнаружения и определения количества ошибок, регистр количества стертых символов, первый, второй и третий коммутаторы данных, счетчик количества исправленных символов, дешифратор, регистровый файл значений ошибок, блок управления коррекцией, буфер значения ошибки, m-разрядный сумматор по модулю q, элемент И. Параллельное выполнение двух алгоритмов: исправления и исправления с учетом стертых символов - увеличивает быстродействие устройства и реализует два режима работы устройства. Введение блоков принятия решений позволяет гибко менять стратегию декодирования и прогнозировать ситуацию отказа от декодирования. Введение счетчика исправленных ошибок позволяет наряду с прогнозированием количества ошибок проводить контроль работы устройства в процессе декодирования. 4 з.п. ф-лы, 10 ил., 5 табл.

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

Известны способы и устройства защиты информации от ошибок (Бэрлекемп Э. Алгебраическая теория кодирования. М. Мир, 1971, Блейхут Р.Э. Теория и практика кодов, контролирующих ошибки. М. Мир, 1986, Кларк Дж. и Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. М. Радио и связь, 1987, Питерсон У. и Уэлдон Э. Коды, исправляющие ошибки. М. Мир, 1976, Габидулин Э. М. и Афанасьев В. Б. Кодирование в радиоэлектронике. М. Радио и связь, 1986.).

Наибольшее распространение получили коды Рида-Соломона, так как для них разработаны эффективные алгебраические методы декодирования и иттерационные алгоритмы Бэрлелемпа-Месси.

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

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

Внутренний (внешний) код производит декодирование кодовых слов с учетом флагов стирания, что значительно повышает эффективность кода. Например, применяется внешний код Рида-Соломона (105, 100) над полем Галуа GF(265), позволяющий обнаружить и исправить до двух ошибок. Тогда внутренний код (55,50) может обнаружить и исправить до двух ошибок или пять стираний.

Известны устройства для декодирования кодов Рида-Соломона (Ко С.С. and Tjhung T.T. Simple programmable processor for decoding Reed-Solomon codes in compact disc devices at high speed. INТ. J. Еlectronics, 1989, vol. 67, no. 16p. 15-25; европейский патент N 0061345, 1981, европейский патент N 0136587, 1983).

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

Известны другие устройства декодирования кодов Рида-Соломона (Муттер В. М. и др. Микропроцессорные кодеры и декодеры. М. Радио и связь, 1991, с. 65-75.

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

Известно устройство быстрого декодирования кодов Рида-Соломона (Arvind М. Patel "On-the-fly decoder for multiple byte errors", IВM Journal of Research and Development, vol. 3, по.3, 1986). Предложенный алгоритм реализует быструю процедуру исправления с попыткой предсказать отказ от декодирования. Однако он не реализует процедуру исправления стираний и использует процедуру Ченя, следовательно, отказ от декодирования подтверждается только после проверки на возможность исправления последнего символа кодового слова.

Наиболее близким к предлагаемому является устройство (европейский патент N 0096109, кл. G 06 F 11/10, 1982).

Устройство содержит буфер данных, вычислитель полинома локаторов ошибок, вычислитель синдромов, буферный региcтр cиндромов (регистровый файл), определитель локаторов ошибок, блок вычисления значения ошибок.

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

Цель изобретения расширение области применения устройства и повышение его быстродействия при декодировании кодов Рида-Cоломона с учетом стираний.

Поставленная цель достигается тем, что в известное устройство, содержащее буферный регистр данных (БР), вычислитель синдромов (ВС), блок управления и синхронизации (БУ), первый счетчик символов кодового слова (1СБ), причем связи выполнены так, что первая группа информационных входов БР является первой группой информационных входов устройства и соединена с группой информационных входов ВС, первая группа управляющих входов блока управления является первой группой управляющих входов устройства, введены счетчик флагов стирания (СФС), генератор локаторов (ГЛ), схема управления записью номеров стертых символов и их локаторов (СЭНЛ), дешифратор количества флагов (ДКФ), регистровый файл номеров стертых символов (РФН), регистровый файл локаторов стертых символов (РФЛ), первый и второй блоки принятия решений (1БПР, 2БПР), блок стираний (БС), блок обнаружения и определения количества ошибок (БОО), регистр количества стертых символов (РСС), первый, второй и третий коммутаторы данных (1МХ, 2МХ, 3МХ), блок регистрации ошибок кодового слова (БРО), вычитающий счетчик количества исправленных (скорректированных) символов (СИС), дешифратор (ДШ), второй счетчик символов кодового олова (2CБ), регистровый файл номеров символов (РФКС), подлежащих коррекции, регистровый файл значений ошибок (РФЗО), блок управления коррекцией (БУК), буфер значения ошибки (БЗО), n-разрядный сумматор по модулю m (СМ), схема И, причем информационный вход счетчика флагов стирания является информационным входом флагов стираний устройства, вторая управляющая группа блока управления и синхронизации является второй управляющей группой режима работы устройства, первая группа управляющих выходов блока управления и синхронизации соединена с управляющими входами вычислителя синдромов, первого счетчика символов кодового cлова, генератора локаторов, первыми группами управляющих входов счетчика флагов стирания, схемы управления записью номеров стертых символов и их локаторов соответственно, вторая группа управляющих выходов блока управления и синхронизации соединена с первыми группами управляющих входов первого и второго блоков принятия решений, регистра количества стертых символов, блока обнаружения и определения количества ошибок, блока регистрации ошибок кодового cлова, блока управления коррекцией, счетчика количества исправленных символов, группами управляющих входов второго счетчика символов кодового cлова, регистрового файла номеров символов кодового cлова, регистрового файла значений ошибки и блока стирания соответственно, информационная группа выходов вычислителя синдромов соединена с первой информационной группой первого блока принятия решений, информационная группа выходов которого соединена с первой информационной группой входов блока стирания, информационной группой блока обнаружения и определения количества ошибок и второй группой управляющих входов блока регистрации ошибок кодового cлова соответственно, группа управляющих выходов первого блока принятия решений соединена с вторыми группами управляющих входов блока обнаружения и определения количества ошибок, второго блока принятия решений, третья управляющая группа входов блока управления и синхронизации соединена с первой группой управляющих выходов дешифратора количества флагов, второй группой управляющих входов первого блока принятия решений, первой информационной группой второго блока принятия решений и информационной группой входов регистра количества стертых символов, информационная группа выходов которого соединена с первой группой входов первого коммутатора данных, группа выходов которого соединена с группой входов загрузки счетчика количества исправленных символов, выходы которого соединены с входами дешифратора, выходы которого соединены с третьей группой управляющих входов блока регистрации ошибок кодового cлова, выход которого является выходом флага ошибки декодирования устройства, выходы счетчика флагов стирания соединены с входами дешифратора количества флагов и второй группой управляющих входов схемы управления записью номеров стертых символов и их локаторов, управляющая группа выходов которого соединена с управляющими входами регистрового файла номеров стертых символов и регистрового файла локаторов стертых символов соответственно, вторая группа управляющих выходов дешифратора количества флагов соединена с второй группой управляющих входов счетчика флагов стирания, информационная группа выходов первого счетчика символов кодового слова соединена с группами информационных входов регистрового файла номеров стертых символов, генератора локаторов, схемы управления записью номеров стертых символов и их локаторов и блока управления и синхронизации соответственно, информационная группа выходов генератора локаторов соединена с информационной группой входов регистрового файла локаторов стертых символов, группа информационных выходов которого соединена с второй группой информационных входов блока стирания, информационная группа выходов которого соединена с первой группой входов третьего коммутатора данных, группа выходов которого соединена с группой информационных входов регистрового файла значений ошибок, группа информационных выходов которого соединена с группой информационных входов буфера значений ошибки, группа управляющих входов которого соединена с первой группой управляющих выходов блока управления коррекцией, второй управляющий выход которого соединен с вторым управляющим входом счетчика количества исправленных символов и с первой группой входов элемента И, вторая группа входов которого соединена с группой информационных выходов буфера значений ошибки, группа выходов элемента И соединена с первой группой m-разрядного сумматора по модулю q, вторая группа входов которого соединена с группой информационных выходов буферного регистра, а группа выходов сумматора является группой информационных выходов устройства, информационная группа выходов регистрового файла номеров стертых символов соединена с первой группой входов второго коммутатора данных, группа выходов которого соединена с группой информационных входов регистрового файла номеров символов, подлежащих коррекции, группа информационных выходов которого соединена с первой группой информационных входов блока управления коррекцией, вторая группа информационных входов которого соединена с группой информационных выходов второго счетчика символов кодового cлова, первая группа управляющих выходов второго блока принятия решений соединена с группами управляющих входов первого, второго и третьего коммутаторов данных соответственно, вторая группа управляющих выходов второго блока принятия решений соединена с четвертой группой управляющих входов блока регистрации ошибок кодового олова и второй группой входов первого коммутатора данных, первая группа информационных выходов блока обнаружения и определения количества ошибок соединена с второй группой входов третьего коммутатора данных, вторая группа информационных выходов блока обнаружения и определения количества ошибок соединена с второй группой входов второго коммутатора данных, выход флага ошибки блока обнаружения и определения количества ошибок соединен с третьим управляющим входом второго блока принятия решений.

В зависимости от задания режима работы устройство производит или декодирование внешнего кода с исправлением ошибок, а при отказе от декодирования помечает все кодовое слово флагом стирания, или декодирование внутреннего кода с учетом флагов стирания. При декодировании с учетом флагов стирания устройство вначале определяет стратегию декодирования. Если количество стираний удовлетворяет условию t+1<=N(F_{)<=2t+1 для кодов, например, с количеством проверочных символов, равном 5, то разрешается работа блока стирания. Параллельно блок обнаружения и определения количества ошибок пытается провести декодирование самостоятельно. При успешном завершении блок обнаружения и определения количества ошибок игнорирует сообщения блока стирания, в противном случае информация блока стирания используется блоком коррекции для исправления стираний.}

Существенным отличием предлагаемого устройства от прототипа и других аналогичных устройств является параллельное и независимое функционирование двух алгоритмов: стирания и обнаружения ошибок, что значительно повышает быстродействие устройства и расширяет его функциональное применение. Первый и второй блоки принятия решений принимают решения: отказ от использования алгоритма стираний, если t+1>N(F_ст)>2t+1 и запуск только алгоритма обнаружения; принятие решений при выполнении условий t+1<=N(F_{)<=2t+1: используется информация блока обнаружения, если он определил, что количество ошибок не более двух и в противном случае используется информация блока стирания.}

Блок коррекции использует полученную информацию для исправления ошибочных символов.

Блок принятия решений (1БПР), анализируя значения синдрома и информацию о количестве стираний, может предсказать реальную ситуацию: попытку декодирования и полный отказ от декодирования.

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

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

На фиг.1 дана структурная схема устройства; на фиг.2 вариант выполнения вычислителя синдромов; на фиг.3 вариант выполнения генератора синдромов; на фиг. 4 структурная схема варианта выполнения первого блока принятия решений; на фиг. 5 блок стираний; на фиг.6 и 7 вариант выполнения блока стирания; на фиг. 8 структурная схема блока обнаружения и определения количества ошибок; на фиг. 9 и 10 алгоритм функционирования устройства для режима исправления ошибок и стираний (при работе в режиме обнаружения и исправления ошибок и установок флагов стирания работа блока стирания исключается из алгоритма).

Используются следующие обозначения: Din входные символы кодового олова (вектора), подлежащие декодированию, Dout выходные данные БР, подлежащие выдаче и/или исправлению из декодера; FL флаги стираний; Е_i- значение i-ой ошибки, N_i значение номера символа, соответствующее i-ой ошибке, Х_i значение локатора для стертого N_i символа.

Предлагаемое устройство (фиг.1) состоит из буферных регистров 5 и 20 данных (БР). Условное разбиение БР, выполненного как, например, последовательный сдвиговый регистр с разрядностью n-бит, сделано из расчета, что длина регистра 5 определяется количеством символов кодового cлова, а длина регистра 20 задержкой декодирования. Устройство также содержит блок ВС 6, СФС 7, 1СБ 8, ГЛ 9, СЗНЛ 10, блок 11 управления и синхронизации, ДКФ 12, РФН 13, РФЛ 14, 1БПР 15, БС 16, БОО 17, РСС 18, 2БПР 19, коммутаторы: 1МХ 21, 2МХ 22, 3МХ 23, БРО 24, СИС 25, ДЩ 26, 2СБ 27, регистровый файл номеров символов, подлежащих коррекции (РФКС) 28, РФЗО 29, БУК 30, БЗО 31, элемент И 32, n-разрядный сумматор по модулю m (СМ) 33.

На фиг. 1 также показаны группа 1 информационных входов устройства Din, вход 2 флагов стирания, первая управляющая группа 3 входов устройства, вторая управляющая группа 4 задания режимов работы устройства, блок 34 коррекции (входящие в него блоки), выход 35 флага ошибки декодирования устройства, информационная группа 36 выходов устройства, Dout выходные символы БР.

Вычислитель синдромов (ВС) содержит (фиг.2) СМ 39-43, регистры 44-48, блоки умножения: на элемент поля ¹ 49, на элемент ² 50, на элемент ³ 51, на элемент ⁴ 52. На фиг.2 также показаны входная шина 38 символов Din, выходы 53 значений синдромов S_i.

Генератор локаторов (фиг.3) содержит регистры "Защелки" 59-66 на триггерах с установкой и сбросом, сдвиговые регистры 67-74 c обратными связями, элементы И-НЕ 75-90, выходные инверторы-умощнители 91-98, сумматоры по модулю 2 99-101. На фиг. 3 также показаны: 56 начальная установка регистра "защелки", 57 управление сдвигом регистров 67-74, 58 загрузка начального значения регистра. Группа выходов Z8-Z1 образуют группу выходов текущего значения локатора. Группа входов 55 (D7-D0) может быть использована для загрузки начального значения локатора.

Первый блок принятия решения (1БПР) содержит (фиг.4) первый 111, второй 112, третий 113, четвертый 114, пятый 115 регистры хранения значений синдромов S_i, первый 116, второй 117, третий 118, четвертый 119, пятый 120, шестой 138, седьмой 139, восьмой 140, девятый 141, десятый 155, одиннадцатый 156 m-входовые элементы ИЛИ-НЕ, первый 121, второй 122, третий 147, четвертый 157, пятый 143 элементы И-НЕ, двенадцатый элемент ИЛИ-НЕ 145, первый 123, второй 126, третий 128, четвертый 129, пятый 132, шестой 134, седьмой 135, восьмой 149, девятый 150, десятый 151 умножители (УМ) в поле Галуа GF(q^m), первый 124, второй 127, третий 130, четвертый 133, пятый 136, шестой 153, седьмой 154 m-разрядные сумматоры по модулю q (СМ), первый 142, второй 148, третий 146, элементы НЕ, элемент И 144, первый 125, второй 131, третий 137, четвертый 152 блоки возведения в квадрат элементов поля Галуа.

Связи выполнены так, что группа информационных входов всех регистров является группой информационных входов блока, группа управляющих входов всех регистров является группой управляющих входов блока, информационные группы выходов первого, второго, третьего, четвертого, пятого регистров соединены с группами входов первого, второго, третьего, четвертого, пятого элементов ИЛИ-НЕ соответственно и совместно с группами выходов первого, второго, третьего, четвертого, пятого сумматоров являются группой информационных выходов блока, группы выходов первого, второго, третьего, пятого сумматоров дополнительно соединены с группами входов шестого, седьмого, восьмого, девятого элементов ИЛИ-НЕ соответственно, выход первого элемента ИЛИ-НЕ соединен с первыми входами первого и второго элементов И-НЕ соответственно, выходы второго, третьего, четвертого, пятого элементов ИЛИ-НЕ соединены с вторым, третьим, четвертым, пятым входами первого элемента И-НЕ, выход которого является выходом НЕТ ОШИБОК в группе управляющих выходов блока, выход шестого элемента ИЛИ-НЕ соединен с вторым и первым входами второго элемента И-НЕ и двенадцатого элемента ИЛИ-НЕ соответственно, выход седьмого элемента ИЛИ-НЕ соединен с третьим и вторыми входами второго элемента И-НЕ и двенадцатого элемента ИЛИ-НЕ cоответственно, выход восьмого элемента ИЛИ-НЕ cоединен с четвертым и третьим входами второго элемента И-НЕ и двенадцатого элемента ИЛИ-НЕ соответственно, выход девятого элемента ИЛИ-НЕ cоединен с пятым входом второго элемента И-НЕ, выход которого соединен с входом первого элемента НЕ и первым входом пятого элемента ИЛИ-НЕ соответственно, выход последнего соединен с первым входом элемента И, второй вход которого является вторым управляющим входом блока, выход двенадцатого элемента ИЛИ-НЕ cоединен с первым входом третьего элемента И-НЕ, выход которого соединен с входом второго элемента НЕ и вторым входом пятого элемента ИЛИ-НЕ, группа информационных выходов первого регистра дополнительно соединена с первыми группами входов первого и второго умножителей и группой входов второго блока возвещения в квадрат, группа выходов которого соединена с второй группой входов третьего сумматора, группа информационных выходов второго регистра дополнительно соединена с первыми группами входов третьего, четвертого и шестого умножителей, группа информационных выходов третьего регистра дополнительно соединена с вторыми группами входов первого, третьего, пятого и седьмого умножителей, группа информационных выходов четвертого регистра дополнительно соединена с вторыми группами входов второго, четвертого умножителей, первой группой входов пятого умножителя и группой входов третьего блока возведения в квадрат соответственно, группа информационных выходов пятого регистра дополнительно соединена с второй группой шестого умножителя, и первой группой входов седьмого умножителя соответственно, группа выходов первого умножителя соединена с первой группой входов первого сумматора, вторая группа которого соединена с группой выходов первого блока возведения в квадрат, группа выходов второго умножителя соединена с первой группой входов второго сумматора, вторая группа входов которого соединена с группой выходов третьего умножителя, группа выходов четвертого умножителя соединена с первой группой третьего сумматора, группа выходов пятого умножителя соединена с первой группой входов четвертого сумматора, вторая группа входов которого соединена с группой выходов шестого умножителя, группа выходов седьмого умножителя соединена с первой группой входов пятого сумматора, вторая группа выходов которого соединена с группой входов третьего блока возведения в квадрат, группа выходов первого сумматора дополнительно соединена с первой группой входов девятого умножителя и группой входов четвертого блока возведения в квадрат, группа выходов которого соединена с первой группой входов седьмого сумматора, группа выходов которого соединена с группами входов одиннадцатого элемента ИЛИ-НЕ, выход которого соединен с вторым входом третьего элемента И-НЕ, группа выходов второго сумматора соединена с вторыми группами входов восьмого и девятого умножителей, группа выходов последнего соединена с первой группой входов шестого сумматора, группа выходов которого соединена с группой входов десятого элемента ИЛИ-НЕ, выход которого соединен с вторым входом четвертого элемента НЕ, группа выходов третьего сумматора дополнительно соединена с первой группой входов десятого умножителя, группа выходов которого соединена с второй группой входов седьмого сумматора, группа выходов четвертого сумматора дополнительно соединена с второй группой входов десятого умножителя, группа выходов пятого сумматора дополнительно соединена с первой группой входов восьмого умножителя, группа выходов которого соединена с второй группой входов шестого сумматора, выход первого элемента НЕ, выход второго элемента НЕ и выход элемента И являются выходами ОДНА ОШИБКА, ДВЕ ОШИБКИ и НЕИСПРАВИМАЯ ОШИБКА cоответствен-но в группе управляющих выходов блока.

На фиг.4 также показаны: 103 группа информационных входов значения синдромов S_i, 104 управление записью в регистр синдромов, 105 начальная установка регистра синдромов, 110 выход ое НЕТ ОШИБКИ, 108 выход 1_е ОДНА ОШИБКА, 107 выход признака UЕ НЕИСПРАВИМАЯ ОШИБКА, 109 выход 2_е ДВЕ ОШИБКИ.

Блок стираний (фиг.5) содержит первый 178, второй 179, третий 180, четвертый 181, пятый 182, шестой 183 регистры соответственно, первый 184, второй 185, третий 186, четвертый 187 коммутаторы данных, пятый 196, шестой 199, седьмой 195, восьмой 198, девятый 200, десятый 197, одиннадцатый 201, двенадцатый 202 коммутаторы данных, первый 188, второй 189, третий 190, четвертый 191, пятый 192, шестой 193 сумматоры (СМ) по модулю q, первый 203, второй 204, третий 205, четвертый 206, пятый 207 умножители (УМ), блок 208 операций с локаторами, элемент И 194.

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

На фиг.5 также изображены 158 первая группа информационных входов блока; 159-164 шины управления регистрами, 174-177, 166-173 шины управления коммутаторов, которые образуют первую группу управляющих входов блока совместно с управляющим входом 165 элемента И 144, 209-213 выходы значений ошибок е₅, е₄, е₃, е₂, е₁ информационная группа выходов блока, U вторая группа управляющих входов блока, Х вторая группа информационных входов блока.

Блок 208 операций с локаторами (БС) содержит (фиг.6) первый 214 и второй 215 коммутаторы данных с памятью, сумматор (СМ) 216, третий коммутатор 217 данных, определитель 218 обратного элемента (003) поля GF (q^m). На фиг.6 также показаны: Х₁-Х₅ группа информационных входов блока, U₁, U₂, U₃ группа управляющих входов блока; Z группа информационных выходов блока 208.

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

Регистры 178-183 (фиг.5) содержат (фиг.7), m D-триггеров 231 и 232, 2m элементов И-НЕ 225-228, элементы НЕ 229 и 230.

На фиг. 7 также показаны 224 группа информационных выходов Q_iрегистра, 221 первая группа информационных входов I₁-I_m, 219 вторая группа информационных входов D_o-D_m, 220 вход тактирования С записи по входам D_i, 223 вход НУ записи (установки) по входам I_i.

Блок обнаружения и определения количества ошибок (БОО) [фиг.8] содержит первый 233, второй 234, третий 235 и четвертый 236 умножители (УМ), первый 247, второй 248, третий 249 и четвертый 250 сумматоры (СМ), блок 237 возведения в квадрат элементов поля Галуа, первый 238, второй 239, третий 240 и четвертый 243 коммутаторы данных, ООЭ 251, первый 252, второй 253, третий 254, четвертый 241, пятый 242, шестой 245, седьмой 246, восьмой 258 и девятый 260 регистры, блок 255 решения квадратного уравнения, элемент ИЛИ 256, триггер ошибки 257, блок 244 определения номера символа по локатору элемент И 259.

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

На фиг.8 также обозначены: А₀, А₁, А₂, S₀, S₁ группа информационных входов блока, 2е второй управляющий вход блока, ОШ выход флага ошибки блока; Е₁ и Е₂ первая группа информационных выходов блока; N₁ и N₂ вторая группа информационных выходов блока.

При реализации устройства могут быть применены микросхемы серий 133, 155, 531, 555, 589, 565. Наиболее эффективно выполнение устройства в интегральном исполнении.

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

Рассмотрим реализацию устройства для каскадного кода Рида-Соломона (105, 100) и (55,50) в поле Галуа GF (256).

Применяется код с кодовым расстоянием d= 6=2t+e+1, где t количество ошибок; е количество стираний. Код (105,100) обнаруживает ошибки, исправляет и/или устанавливает флаги стираний. Код (55, 50) обнаруживает и исправляет до двух ошибок или пять стираний. Введение пятого проверочного символа позволяет увеличить обнаруживающую способность кодов с минимальной избыточностью.

Поле Галуа GF(256) задается примитивным элементом а 0000 0010 с порождающим полиномом g(x) Х⁸ + X⁴ + Х² + 1. Кодирование систематическим кодом обоих кодов производится, например, полиномом G(x) (x + 1)(x + a)(х + a²)(x + a³) (x + a⁴), с помощью которого вычисляются пять проверочных символов, расположенных после информационных символов, содержа