Устройство коррекции двойных ошибок с использованием кода Рида-Соломона Советский патент 1991 года по МПК H03M13/47 H03M13/51 

Фиг.1

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

Целью изобретения является повышение быстродействия устройства.

На фиг.1 представлена блок-схема устройства коррекции двойных ошибок с использованием кода Рида-Соломона; на фиг.2 - функциональная схема блока управления; на фиг.З - эпюры напряжений на выходах некоторых элементов блока управления; на фиг.4 - функциональная схема блока деления; на фиг.5 - функциональная схема блока анализа синдрома; на фиг.6 - функциональная схема коммутатора.

Устройство содержит блок 1 деления, буферный регистр 2, блок 3 управления, блок 4 деления, блок 5 совпадения, блок 6 анализа синдрома, коммутатор 7, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 8-11, буферный регистр 12, элементы 13-15 памяти.

Блок 3 управления содержит формирователь 16 прямоугольного импульса, элемент 17 задержки, элемент И 18, счетчик 19 импульсов, триггер 20, тактовый генератор 21, элемент 22 задержки, инвертор 23, коммутатор 24, инвертор 25, элемент И 26, элемент И-НЕ 27, дешифратор 28, элемент И 29, коммутатор 30, счетчик 31 импульсов и элементы ИЛИ 32 и 33.

Коммутатор 7 выполнен на элементах И 34.

Блок 6 анализа содержит группу элементов ИЛИ 35, дешифратор 36 состояния, элементы И 37-40, элемент И -НЕ 41 и элемент ИЛИ 42.

Блок 4 деления содержит коммутаторы 43, параллельные регистры 44 сдвига и сумматоры 45 по модулю два.

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

В устройстве исследуется полиномиальное представление порождающего полинома кода Рида-Соломона

д(х) (х -о21) (х -а) (х -а2)) (х -а3) х х{х-а4),(1)

для исправления двукратных ошибок, где t - кратность ошибки. Для лучшего понимания работы устройства необходимо отметить, что в его основу положен конвеерный вариант устройства коррекции Меггита с - вылавливанием ошибок и символы кодового слова принадлежат полю Галуа GF(2m).

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

0 поступает в блок деления и в буферный регистр 2, информация с которого синхронно с поступлением символов нового кодового слова перезаписывается в буферный регистр 12. К выходам блока 4 деления под5 ключей блок 6 анализа синхрома, контролирующий состояние разрядов синдрома и вырабатывающий при определенном значении управляющие сигналы. При обнаружении им в одной из декодируемых

0 комбинаций синдрома одно или двукратных ошибок соответственно вида , ОазОач OOazai, OOOai, где ai, 32, аз, а4 - коэффициенты, на которые корректируются соответствующие символы кодового слова, на

5 выходах устанавливаются управляющие сигналы. Один из них, поступая на второй вход блока 5 совпадения, открывает его и соответствующий коэффициент, стоящий в последней, счет слева направо, ячейке вто0 рого блока 4 деления, поступает обратно, где происходит их взаимное вычитание. Одновременно с этим по другому управляющему сигналу отпирается канал коммутатора 7 и этот же коэффициент поступает на первые

5 входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 8, а на вторые входы приходят перезаписываемые символы декодируемого слова и происходит исправление первой ошибки. Аналогичен процесс декодирования, если

0 есть и вторые ошибки. Однако порядок коррекции ошибок изменяется, если декодируемая комбинация синдрома вычислена, а также, начиная с (2п - г + 1), где п - количество символов в слове; г - число провероч5 ных символов и г 2t и за время, оставшееся до конца цикла, кратного п, вторая ошибка не успевает быть исправлена вышеизложенным способом Блок 3 управления вырабатывает сигнал, по которому блок 6 анализа

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

5 При этом каналы коммутатора 7 соединяют выходы второго блока 4 деления так, чтобы ат поступал на элемент 8, аа - на элемент 11, аз - на элемент 10, 34 - на элемент 9, на другие входы которых поступают соответствующие символы кодового слова, подлежащие декодированию. После исправления ошибок, если таковые были, по команде с блока 3 управления блок 6 анализа синдрома отключается и оставшиеся в буферном регистре 12 символы поступают на выход.

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

Буферный регистр 2 обеспечивает посимвольный прием и хранение поступающей информации.

Блок 3 управления предназначен для выработки служебных сигналов, необходимых для работы устройства и обеспечивает: первоначальную установку в нулевое состояние блока 1 деления, блока 4 деления и своих внутреннихэлементов; импульсы синхронизации для работы всего устройства и внешнего источника информации; сигналы перезаписи из блока 1 деления в блок 4 деления; сигнал ы блокировки некоторых элементов до такта (2п - г) и перевода в неактивное состояние в такте от (2п - г + 1), если ошибки обнаружены и исправлены, блоком 6 анализа синдрома. Сформированный отрицательный импульс необходим для установки в начальное состояние элементов блока 4 деления и через элемент И 18 элементов блока 1 деления, счетчик 19 импульсов, триггер 20. После этого прямоугольные импульсы с тактового генератора 21 поступают на выход блока 3 управления и всего устройства, а также на счетчик 19, который обеспечивает подсчет числа импульсов, соответствующих числу символов декодируемого кодового слова. Кроме того, импульсы подаются на вход элемента 22 задержки, обеспечивающий задержку сигнала на время, равное времени установления очередного состояния на выходе счетчика 19/ Такой режим обеспечивает одновременное установление внутренних элементов блока 3 управления, зависящее от состояния счетчика 19 и поступление тактовых импульсов. С выхода элемента 22 задержки сигнал поступает на тактовые входы буферных регистров 2 и 12 блока 1 деления и на вход инвертора 23, инвертирующего тактовые импульсы. Прямые и инверсные тактовые импульсы поступают на соответствующие входы коммутатора 24, управление по каналам сигналов которого осуществляется соответственно инверсным и прямым управляющими сигналами. Инверсный управляющий сигнал получается инвертированием прямого на инверторе 25, который приходит с элемента И 26. Последний обеспечивает состояние логического нуля 5 на своем выходе сигналом низкого уровня, поступающим с выхода элемента И-НЕ 27, изменяющее свое состояние на противоположное только в момент установления на счетчике 19 состояния соответствующего

0 последнему п такту. Такой режим работы управляющих сигналов коммутатора 24 обеспечивает формирование в отличие от других тактов двух импульсов синхронизации в одном n-м такте для блока 4 деления.

5 По первому импульсу происходит обычная операция деления, а по второму - перезапись состояния блока 1 деления в блок 4 деления. К выходам счетчика 19 подключен также дешифратор 28, обеспечивающий из0 менение выходного состояния из нуля в единицу, при установлении на выходе счетчика 19 соответствующих (2п - г + 1) такту. Единичный сигнал разрешает прохождение информации о наличии ошибки через элемент

5 И 29, если таковая имеется, от блока 6 анализа синдрома. При этом необходимо наличие единичного сигнала на входе элемента И 29 с коммутатора 30. Коммутатор, начиная с ( r + 1) такта, сравнивает номер такта

0 и вид синдрома, соответствующего декодируемой комбинации двукратной ошибки, если таковой определяется. Если число оставшихся тактов до 2 недостаточно для исправления двух ошибок последователь5 ным способом, на выходе элемента И 29 устанавливается единица. Информация о номере такта поступает со счетчика 31, запускаемого сигналом с дешифратора 28, а импульсы счета - с тактового генератора 21.

0 Данные о виде синдрома поступают на коммутатор 30 с элементов ИЛИ 32 и 33, а также на прямую с блока 6 анализа синдрома. На каждый вход поступает информация о том синдроме, при котором ошибка уже после5 довательно исправлена быть не может. При этом вход соответствует определенному номеру такта и виду синдрома: первый - (2п - -г + 1) и , второй с элемента ИЛИ 32 и (2п - г + 2) такту, третий - с элемента ИЛИ

0 33 и (2п - г -г 3) такту. Элемент ИЛИ 32 анализирует информацию о синдромах вида , ОазОат. элемент ИЛИ 33 - о синдромах вида азООат, OOaaai, ОазОат.

Информация с выхода элемента И 29

5 (2п - г ± 2) или любым до 2п включительно тактовым импульсом заносится в триггер 20 и блокирует работу блока 6 анализа синдрома. Такой режим необходим, что5ы исключить в оставшихся до 2п тактах обнаружение ложных ошибок, обусловленных тем. что с

(2n-r+ 1)такта коррекция синдрома в блоке 4 деления не производится, если ошибки исправляются одновременно. С выхода элемента И 26 сигналом логической единицы обеспечивается; переключение внутренних коммутаторов 43 блока 4 деления, необходимых при перезаписи синдромов; сброс в начальное состояние, через элемент 17 задержки и элемент. И 18, блока 1 деления, триггера 20, счетчика 19. Элемент 17 задержки задерживает импульс сброса в n-м такте, исходя из времени, необходимого для завершения всех вычислительных операций в устройстве.

Блок 4 деления выполняет те же функции и выполнен по той же схеме, что и блок 1 деления. Отличительной особенностью является наличие внутренних коммутаторов 43. Они в n-м такте по сигналу с блока 3 управления переходят из режима сквозного канала в режим приема с внешнего устройства, по вторым входам, В данном случае это передача сигналов с выходов первого блока 1 деления на входы блока 4 деления для последующей записи и использования в качестве делимого.

Блок 5 совпадения обеспечивает пропуск сигналов с соответствующей ячейки при обнаружении ошибки в блоке 6 анализа синдрома и поступлении соответствующего сигнала на второй вход схемы. Для этих целей можно использовать микросхемы 1533КП16, у которых по первым входам поступает сигнал, а вторые входы заземлены.

Блок 6 анализа синдрома предназначен для обнаружения декодируемой комбинации синдрома, управления коммутатором 7 и блока 5 совпадения, выработке и передаче необходимых, сигналов для блока 3 управления.

Б.ЛОК 6 работает следующим образом. Сигналы, поступающие с первых, вторых, третьих и четвертых выходов блока 4 деления, подаются на входы соответствующих элементов ИЛИ 35. Схемы определяют отличие от нуля значений этих сигналов соответствующих коэффициентам синдрома дешифратора 36 при наличии на его первых входах, с элементов ИЛИ 35, синдрома соответствующего вычисляемой комбинации двукратных ошибок, устанавливает на соответствующем выходе, подключенном к элементам И 37-39 или 40 нулевой сигнал. Определенный элемент И, где соответствие; 3400ai - 40, ОазОат - 39, 003231 - 38, OOOai - 37, переключается в единичное состояние только при наличии единицы, поступающей с блока 3 управления в такте, начиная с 2п- - г + 1 на втором входе. Одновременно с этим, сигналы со всех выходов дешифратора 36 поступают на выход блока и на входы элемента И-НЕ 41. На его выходе появляется сигнал логической единицы при наличии дешифрируемой комбинации ошибки, поступающей в блок 3 управления и в блок 5 совпадения, а также на второй вход элемента ИЛИ 42. Первый его вход соединен с выходом элемента И 37. Такое включение элемента ИЛ И 42 позволяет блоку 6 анализа

0 синдрома как управлять соответствующим каналом коммутатора 7 при последовательном режиме исправления ошибок при обнаружении их в тактах до (2п -г), так и работать в режиме одновременного исправления

5 ошибок, используемом в тактах с (2п - г 1). При обнаружении двукратной ошибки в тактах с (2п - г + 1) на выходе элемента И 37 соответствующей аз, аз или аз появляется логическая единица, одновременно с этим в

0 единичное состояние переключается и элемент ИЛИ 42. Эти единичные уровни поступают на входы управления соответствующих каналов коммутатора 7 и открывают их.

Коммутатор 7 обеспечивает прохожде5 ние сигналов, равных значению, на которое корректируется символ декодируемого слова, на соответствующие элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 8-11 в зависимости от вида синдрома.

0 Предлагаемое устройство коррекции двойных ошибок с использованием кода Рида-Соломона по сравнению с известным повышает быстродействие конвейерных устройств коррекции за счет изменения

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

Формула изобретения

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

5 регистра и являются информационными входами устройства, первые - четвертые выходы первого блока деления подключены к одноименным входам второго блока деления, первые выходы которого подключены к

0 первым входам блока совпадения, выходы первого буферного регистра подключены к первым входам первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ , выходы которого подключены к информационным входам второго

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

коммутатор и последовательно соединенные первый элемент памяти, третий элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, второй элемент памяти, четвертый элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и третий элемент памяти, выход которо- го является информационным выходом устройства, первый выход блока анализа синдрома прдключен к первому входу блока управления и второму входу блока совпадения, выходы которого и первый выход блока управления подключены соответственно к пятым и шестому входам второго блока деления, вторые - четвертые выходы которого подключены соответственно к первым - третьим входам блока анализа синд- рома и коммутатора, четвертый вход которого объединен с четвертым входом блока анализа синдрома и подключен к первому выходу второго блока деления, второй - шестой выходы блока управления подклю- чены соответственно к седьмому и восьмому входам второго блока деления, второму входу первого блока деления, пятому и шестому входам блока анализа синдрома, второй - пятый и шестой выходы которого подключены соответственно к пятому - восьмому входам коммутатора и вторым входам блока управления, седьмой выход которого является тактовым выходом устройства, а восьмой выход подключен к третьему входу первого блока деления и тактовым входам первого и второго буферных регистров и первого - третьего элементов па мяти, выходы второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ подключены к инфор- мационным входам первого элемента памяти, вторые входы первого - четвертого элементов ИСКЛЮЧАЮЩЕЕ ИЛИ подключены соответственно к первым - четвертым выходам коммутатора.

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

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

Фиг.з

Изобретение относится к вычислительной технике, а именно к устройствам контроля запоминающих устройств, и может быть использовано для повышения достоверности информации, хранимой в запоминающих устройствах. Целью изобретения является повышение быстродействия устройства. Устройство содержит блок 1 деления, буферный регистр 2, блок 3 управления, блок 4 деления, блок 5 совпадения, блок 6 анализа синдрома, коммутатор 7, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 8 - 11, буферный регистр 12, элементы 13 - 15 памяти. 1 з.п. ф-лы, 6 ил.

0/пЦК1) л

о/пц.1(г)

UW

О/л Ц.1(3)

IL

ОтЦ1(4)

W,W

(51(2)

16),11}

Фиг. 5