УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ КОДА РИДА - СОЛОМОНА Российский патент 1994 года по МПК H03M13/00 

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

В рекомендации МККР 657 по цифровой видеозаписи для защиты видеоданных от ошибок предлагается использовать код Рида-Соломона (32.30) (Хлебородов В. А. Международная рекомендация по цифровой видеозаписи. Видеофонограмма, программная дорожка, кодирование видеоданных. Техника кино и телевидения, 1986, N 3, стр. 45), где 30 - число информационных байт (в общем случае k) а 32 - общее число байт (в общем случае n), включая и 2 проверочных (n - k). Причем (n - k) проверочных байт получаются из информационных как остаток от деления многочлена информационных байт на порождающий многочлен поля Галуа GF(2⁸)
f(x)= x⁸⊕x⁴⊕x³⊕x²⊕x⁰.

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

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

Из поступающей на вход декодера последовательности определяются синдромы S0, S1, S2 и подсчитывается число флагов стираний N, которые сопровождают стертые байты. Если число стираний N = 1 или 2, то вычисляются значения ошибок в стертых байтах и осуществляется их корреляция. В остальных случаях все информационные байты передаются на выход вместе с флагами (если их больше двух) или без них, если флагов не было.

Недостаток прототипа заключается в том, что в его схеме производится только исправление двух стираний.

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

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

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

Как известно, декодер кода (32, 30) Рида-Соломона по своим корректирующим свойствам позволяет гарантийно исправлять однократную ошибку (т. е. один ошибочный байт из 32 без маски, при этом число стираний N = 0) или исправлять не более двух стираний (т. е. один или два помеченных стираниями байта).

На фиг. 1 приведен общий алгоритм декодирования кодом (32, 30), где рассмотрены все возможные ситуации, которые могут возникать в процессе декодирования (см. Разработка и исследование кодека корректирующего кода Рида-Соломона для высокоскоростного видеотракта студийного цифрового видеомагнитофона. Заключительный отчет по теме 052-89-09, выполненный по договору с ВНИИТ, гос. рег. N 018900 38301, ЛЭИС, 1990). Из указанного алгоритма следует, что маскирование всего выходного блока без исправления ошибок или стираний происходит тогда, когда только один из синдромов отличен от нуля (S1 или S0) и блок не содержит флагов стираний. Такая ситуация может возникнуть, если в блоке будут две или более ошибок. Кроме того, если в блоке имеется одно стирание (N = 1) и уравнение S0 * X1 = S1 не выполняется, то эта ситуация свидетельствует о наличии, кроме одного стирания, в блоке еще одной или более ошибок, что также может отмечаться маскированием всего блока. И, наконец, весь блок может маскироваться тогда, когда в режиме исправления однократной ошибки уравнение не было выполненным ни на одном из 32 тактов, что также свидетельствует об ошибке более, чем однократной.

Новизна и отличительные особенности данного устройства по сравнению с прототипом заключаются в том, что вводятся блок запоминания значения стираний, блок запоминания значения синдрома S0, блок запоминания локатора ошибки, блок исправления стираний, блок формирования маски, что позволяет повысить помехоустойчивость декодирующего устройства за счет дополнительного (по сравнении с прототипом) обнаружения ошибок кратности 2 и более при отсутствии стираний или 1 и более при наличии стираний при сохранении возможности прототипа исправлять два стирания. Таким образом, имеются отличительные признаки по сравнению с прототипом и поэтому предлагаемое устройство удовлетворяет критерию "новизны".

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

На фиг. 2 представлена структурная схема предлагаемого декодирующего устройства.

Она содержит блок вычисления синдромов 1 и блок буферного накопителя 2, входы которых объединены и являются информационными входами устройства 3, контрольный вход (стираний) 4 соединен с входом счетчика стираний 5, выход которого соединен с третьим входом введенного блока индикации однократной ошибки 6, первый и второй входы которого соединены с соответствующими выходами блока вычисления синдромов 1. Первый вход синхронизации 7 подключен к блокам 1, 2 и 5. Второй вход синхронизации 8 соединен с блоками 1 и 5. Первый вход блока сумматоров 9 соединен с выходом буферного накопителя 2, второй вход блока сумматоров 9 соединен с выходом введенного блока ИЛИ 10, первый вход которого подключен к выходу блока ключей 11. Выход блока сумматоров 9 является информационным выходом устройства 12. К входу введенного блока 13 запоминания значения стираний подключен контрольный вход 4, а выход блока 13 соединен с четвертым входом введенного блока 17 исправления стираний. Вход введенного блока 14 запоминания S0 соединен с первым выходом блока 1, а выход блока 14 подключен параллельно к первому входу введенного блока 15 вычисления локатора ошибки и третьему входу блока ключей 11, второй вход которого подключен к выходу блока 15 вычисления локатора ошибки, а первый вход блока 11 ключей соединен с вторым выходом блока индикации однократной ошибки, первый выход которого подключен к второму входу введенного блока 16 формирования маски, первый вход которого подключен к второму выходу блока 17 исправления стираний, первый выход которого соединен с управляющими входами блоков 5, 6 и 13. Выход блока 16 является контрольным выходом устройства 18.

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

При поступлении на вход 3 устройства информационных и проверочных работ они записываются в буферный накопитель 2 и одновременно в блоке 1 производится вычисление синдромов S0 и S1. Одновременно подсчитывается счетчиком 5 число стираний N, поступивших на вход 4 стираний. Если S0 и S1 равны нулю, то это означает, что ошибок в блоке нет и он выводится на выход 12 без изменений (см. фиг. 1). Если S0 и S1 не равны нулю и N = 0, то это означает, что в блоке имеется одна или более ошибок. При этом, если в блоке имеется однократная ошибка, то ее локатор X1 = S1/S0. Таким образом, если при последовательном считывании блока с буферного накопителя декодера на одном из 32 тактов будет выполнено равенство S0 * X1 = S1, то это означает наличие однократной ошибки и она исправляется добавлением к данному ошибочному байту синдрома S0. Однако, если ни в одном из 32 тактов это равенство не выполнилось, то это означает, что в блоке ошибки кратности 2 или более и тогда, в отличии от прототипа, маскируется весь блок. Если при N = 0 один из синдромов равен нулю, а другой нет, то эта ситуация может возникать тогда, когда в блоке ошибки кратности 2 или более. При этом также маскируется весь блок. Предложенное устройство по сравнению с прототипом определяет и маскирует весь блок, что и приводит к дополнительному повышению помехозащищенности, так как в прототипе эти ситуации приводили к необнаруженным ошибкам.

При числе стираний N > 3 устройство так же, как и прототип, осуществляет копирование флагов.

При N = 1 или N = 2 устройство так же, как и прототип, производит их исправление. Причем значения ошибок Y1 и Y2 определяются из уравнений
Y1 = (S1 + S0 * X2)(X1 + X2) ** (-1)
Y2 = (S1 + S0 * X1)(X1 + X2) ** (-1), где S0 и S1 - синдромы; Х1 и Х2 - локаторы ошибок (т. е. помеченные байты).

Если стирание одно (N = 1), т. е. известно только Х1, то синдромы S0 = Y1 и S1 = Y1 * X1 и тогда (при Х2 = 0) Y1 = S1/X1, Y2 = 0.

При исправлении одного стирания может возникнуть еще одна ситуация, когда уравнение S0 * X1 = S1 не выполняется, т. е. исправлять стирание нельзя. Это возможно в том случае, когда, кроме одного стирания, в блоке есть еще и ошибки (одна или более). При этом заявляемое устройство по сравнению с прототипом (где эта ситуация не определялась), также маскирует весь блок, что и приводит к дополнительному повышению помехозащищенности.

Предложенное устройство реализовано в виде действующего макета, к которому имеются протоколы испытаний (см. Разработка и исследование кодека корректирующего кода Рида-Соломона для высокоскоростного видеотракта студийного цифрового видеомагнитофона. Заключительный отчет по теме 052-89-09, выполненный по договору с ВНИИТ, гос. рег. N 018900 38301, ЛЭИС, 1990), подтверждающих работоспособность устройства. Устройство реализовано на микросхемах К531 и К556 сериях (В. Н. Шило. Популярные цифровые микросхемы. Справочник. М. : Радио и связь, 1987).

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

Кроме того, к достоинствам устройства может быть отнесено и то, что по сравнению с прототипом, где для исправления двух стираний использовались три синдрома (S0, S1, S2) и, следовательно, три проверочных байта, эта задача, т. е. исправление двух стираний или одной ошибки, а также дополнительное обнаружение еще и части ошибок кратности 2 и более (что не обеспечивал прототип), решена при помощи двух проверочных байт (двух синдромов S0 и S1), что является более эффективным. (56) Авторское свидетельство СССР N 1332539, кл. H 03 M 13/00, 1987.

Авторское свидетельство СССР N 1332532, кл. H 03 M 13/00, 1987.

Изобретение относится к электросвязи и вычислительной технике и может быть использовано для повышения помехоустойчивости в системах передачи и обработки цифровой информации, в частности в цифровой видеозаписи. Целью изобретения является повышение помехозащищенности кода Рида-Соломона. Указанная цель достигается введением в устройство блока 13 запоминания значения стираний, блока 14 запоминания значения синдрома 14, блока 15 вычисления локатора ошибки 15, блока 16 формирования маски и блока 17 исправления стираний, обеспечивающих дополнительное обнаружение части однократных и более ошибок при наличии стираний и части двухкратных и более ошибок при отсутствии стираний. 2 ил.

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