Устройство коррекции двойных ошибок с использованием кода рида-соломона

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛ ИСТИЧ Е С КИХ

РЕСПУБЛИК

М (st)s Н 03 M 13/00 02

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4602050/24 (22) 03:11.88 (46) 07.07.91. Бюл, М 25 (71) Минский радиотехнический институт (72) С.П,Куц (53) 621.394.14 (088,8) (56) Блейхут P. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986, с, 176, Там же, с, 174, рис. 6. 25, (54) УСТРОЙСТВО КОРРЕКЦИИ ДВОЙНЫХ

ОШИБОК С ИСПОЛЬЗОВАНИЕМ КОДА РИДА-СОЛОМОНА

„„Я2„„1662010 А1 (57) Изобретение относится к вычислительной технике, а именно к устройствам контроля запоминающих устройств, и может быть использовано для повышения достоверности информации, хранимой в запоминающих устройствах. Целью изобретения является повышение быстродействия уст-. ройства, Устройство содержит блок 1 деления, буферный регистр 2, блок 3 управления, блок 4 деления, блок 5 совпадения, блок 6 анализа синдрома, коммутатор 7, элементы

ИСКl)ЮЧАЮЩЕЕ ИЛИ 8 — 11, буферный регистр 12. элементы 13 — 15 памяти. 1 э.п, флы, 6 ил.

1662010

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

Целью изобретения является повышение быстродействия устройства, На фиг,1 представлена блок-схема устройства коррекции двойных ошибок с использованием кода Рида-Соломона; на фиг.2 — функциональная схема блока управления; на фиг.3 — эпюры напряжений на выходах некоторых элементов блока управления, на фиг.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 по модулю два.

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

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

g(x) = (х -a ) = (x — а) (х — a )) (х -гР) х х (х-a), (1) для исправления двукратных ошибок, где

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

С информационных входов декодируемое кодовое слово посимвольно заносится в буферный регистр 2 и блок 1 деления, где за время, равное числу тактов, определяемому числом символов кодового слова, вычисляется синдром. После поступления последнего символа принимаемого слова вычисленный синдром перезаписывается в блок 4 деления, а очередное кодовое слово поступает в блок деления и s буферный регистр 2, информация с которого синхронно с поступлением символов нового кодового слова перезаписывается в буферный регистр Т2, К выходам блока 4 деления подключен блок 6 анализа синхрома, контролирующий состояние разрядов синдрома и вырабатывающий при определенном значении управляющие сигналы. При обнаружении им в одной из декадируемых комбинаций синдрома одно или двукратных ошибок соответственно вида а400а1, ОазОа1

00aza>, 000а1, где а1, а2, аз, а4 — коэффициенты, на которые корректируются соответствующие символы кодового слова, на выходах устанавливаются управляющие сигналы. Один из них, поступая на второй вход блока 5 совпадения, открывает его и соответствующий коэффициент, стоящий в последней, счет слева направо, ячейке второго блока 4 деления, поступает обратно, где происходит их взаимное вычитание. Одновременно с этим по другому управляющему сигналу отпирается канал коммутатора 7. и этот же коэффициент поступает на первые входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 8, а на вторые входы приходят перезаписываемые символы декодируемаго слова и происходит исправление первой ошибки.

Аналогичен процесс декодирования, если есть и вторые ошибки, Однако порядок коррекции ошибок изменяется, если декодируемая комбинация синдрома вычислена, а также, начиная с (2n — г+ 1), где и — количество символов в слове; r — число проверочных символов и r = 2t и за время, оставшееся до конца цикла, кратного и, вторая ошибка не успевает быть исправлена вышеизложенным способом. Блок 3 управления вырабатывает сигнал, по которому блок 6 анализа синдрома выдает сигналы на входы коммутатора 7, приводящие к одновременному отпиранию двух каналов, при двукратной ошибке в соответствии с местоположением отличных от нуля коэффициентов синдрома.

При этом каналы коммутатора 7 соединяют выходы второго блока 4 деления так, чтобы а1 поступал на элемент 8, а2 — на элемент 11, аз — на элемент 10, а4 — на элемент 9, на другие входы которых поступают соответствующие символы кодового слова, подлежа1662010

20

40

50

55 ь щие декодированию, После исправления ошибок, если таковые были, по команде с блока 3 управления блок 6 анализа синдрома отключается и оставшиеся в буферном регистре 12 символы поступают на выход, Рассмотрим функциональное назначение каждого из блоков устройства, блок 1 деления предназначен для деления последовательно поступающих символов кодового слова на порождающий полином кода

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

Блок 3 управления предназначен для выработки служебных сигналов, необходимых для работы устройства и обеспечивает: первоначальную установку в нулевое состояние блока 1 деления, блока 4 деления и своих внутренних элементов; импульсы синхронизации для работы всего устройства и внешнего источника информации; сигналы перезаписи из блока 1 деления в блок 4 деления; сигналы блокировки некоторых элементов до такта (2п — r) и перевода в неактивное состояние в такте от (2п — r+ 1), если ошибки обнаружены и исправлены, блоком 6 анализа синдрома, Сформированный отрицательный импульс необходим для установки в начальное состояние элементов блока 4 деления и через элемент И 18 элементов блока 1 деления, счетчик 19 импульсов, триггер 20. После этого прямоугольные импульсы с тактового генератора 21 поступают на выход блока 3 управления и всего устройства, а также на счетчик 19, который обеспечивает подсчет числа импульсов, соответствующих числу символов декодируемого кодового слова. Кроме того, им пул ьс ы подаются на вход элемента 22 задержки, обеспечивающий задержку сигнала на время, равное времени установления очередного состояния на выходе счетчика 19

Такой режим обеспечивает одновременное установление внутренних элементов блока

3 управления, зависящее от состояния счетчйка 19 и поступление тактовых импульсов.

С выхода элемента 22 задержки сигнал поступает на тактовые входы буферных регистров 2 и 12 блока 1 деления и на вход инвертора 23, инвертирующего тактовые импульсы. Прямые и инверсные тактовые импульсы поступают на соответствующие входы коммутатора 24, управление по каналам сигналов которого осуществляется соответственно инверсным и прямым управляющими сигналами, Инверсный управляющий сигнал получается инвертированием прямого на инверторе 25, который приходит с элемента И 26. Последний обеспечивает состояние логического нуля на своем выходе сигналом низкого уровня, поступающим с выхода элемента И вЂ” НЕ 27, изменяющее свое состояние на противоположное только в момент установления на счетчике 19 состояния соответствующего последнему и такту, Такой режим работы управляющих сигналов коммутатора 24 обеспечивает формирование в отличие от других тактов двух импульсов синхронизации в одном и-м такте для блока 4 деления.

По первому импульсу происходит обычная операция деления, а по второму — перезапись состояния блока 1 деления в блок 4 деления, К выходам счетчика 19 подключен также дешифратор 28, обеспечивающий изменение выходного состояния из нуля в единицу, при установлении на выходе счетчика

19 соответствующих (2п — r+ 1) такту. Единичный сигнал разрешает прохождение информации о наличии ошибки через элемент

И 29, если таковая имеется, от блока 6 анализа синдрома. При этом необходимо наличие единичного сигнала на входе элемента

И 29 с коммутатора 30. Коммутатор, начиная с (2n — r + 1) такта, сравнивает номер такта и вид синдрома, соответствующего декодируемой комбинации двукратной ошибки, если таковой определяется. Если число оставшихся тактов до 2 недостаточно для исправления двух ошибок последовательным способом, на выходе элемента И 29 устанавливается единица. Информация о номере такта поступает со счетчика 31, запускаемого сигналом с дешифратора 28, а импульсы счета — с тактового генератора 21.

Данные о виде синдрома поступают на коммутатор 30 с элементов ИЛИ 32 и 33, а также на прямую с блока 6 анализа синдрома. На каждый вход поступает информация о том синдроме, при котором ошибка уже последовательно исправлена быть не может. При этом вход соответствует определенному номеру такта и виду синдрома: первый — {2n—

-г+ 1) и aq00a>, второй с элемента ИЛИ 32 и (2n — r+ 2) такту, третий — с элемента ИЛИ

33 и (2n — r + 3) такту. Элемент ИЛИ 32 анализирует информацию о синдромах вида а<00а<, ОазОа . элемент ИЛИ 33 — о синдромах вида а ООа, 00aza>, ОазОа .

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

1662010

15

25

30 (2п — г+ 1) такта коррекция синдрома в блоке

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

1 деления, Отличительной особенностью является наличие внутренних коммутаторов

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

Блок 5 совпадения обеспечивает пропуск сигналов с соответствующей ячейки при обнаружении ошибки в блоке 6 анализа синдрома и поступлении соответствующего сигнала на второй вход схемы. Для этих целей можно использовать микросхемы 1533КП16, у которых по первым входам поступает сигнал, а вторые входы заземлены, Блок 6 анализа синдрома предназначен для обнаружения декодируемой комбинации синдрома, управления коммутатором 7 и блока.5 совпадения, выработке и передаче необходимых сигналов для блока 3 управления, Цлок 6 работает следующим образом, - Сигналы, поступающие с первых, вторых, . третьих и четвертых выходов блока 4 деления, подаются на входы соответствующих элементов ИЛИ 35. Схемы определяют отличие от нуля значений этих сигналов соответствующих коэффициентам синдрома дешифратора 36 при наличии на его первых входах, с элементов ИЛИ 35, синдрома соответствующего вычисляемой комбинации двукратных ошибок, устанавливает на соответствующем выходе, подключенном к элементам И 37 — 39 или 40 нулевой сигнал, Определенный элемент И, где соответствие, а400а1 — 40, Оаз0а — 39, 00а а1 — 38, 000а1—

37, переключается в единичное состояние только при наличии единицы, поступающей с блока 3 управления в такте, начиная с 2п— r + 1 на втором входе. Одновременно с этим, сигналы со всех выходов дешифрато35

55 ра 36 поступают на выход блока и на входы элемента И вЂ” НЕ 41. Ha его выходе появляется сигнал логической единицы при наличии дешифрируемой комбинации ошибки, поступающей в блок 3 управления и в блок 5 совпадения, а также на второй вход элемента ИЛИ 42, Первый его вход соединен с выходом элемента И 37, Такое включение элемента ИЛИ 42 позволяет блоку 6 анализа синдрома как управлять соответствующим каналом коммутатора 7 при последовательном режиме исправления ошибок при обнаружении их в тактах до (2n — r), так и работать в режиме одновременного исправления ошибок, используемом в тактах с (2п — r + 1).

При обнаружении двукратной ошибки в тактах с (2n — Г + 1) на выходе элемента И 37 соответствующей а, аз или аг появляется логическая единица, одновременно с этим в единичное состояние переключается и элемент ИЛИ 42. Эти единичные уровни поступают на входы управления соответствующих каналов коммутатора 7 и открывают их, Коммутатор 7 обеспечивает прохождение сигналов, равных значению, на которое корректируется символ декодируемого слова, на соответствующие элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 8 — 11 в зависимости от вида синдрома.

Предлагаемое устройство коррекции двойных ошибок с использованием кода

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

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

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

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

1662010

45 коммутатор и последовательно соединенные первый элемент памяти, третий элемент

ИСКЛЮЧАЮЩЕЕ ИЛИ, второй элемент па мяти, четвертый элемент ИСКЛЮЧАЮЩЕЕ

ИЛИ и третий элемент памяти, выход которого является информационным выходом устройства, первый выход блока анализа синдрома подключен к первому входу блока управления и второму входу блока совпадения, выходы которого и первый выход блока управления подключены соответственно к пятым и шестому входам второго блока деления, вторые —. четвертые выходы которого подключены соответственно к первым — третьим входам блока анализа синдрома и коммутатора, четвертый вход которого объединен с четвертым входом блока анализа синдрома и подключен к первому выходу второго блока деления, второй — шестой выходы блока управления подключены соответственно к седьмому и восьмому входам второго блока деления, второму входу первого блока деления, пятому и шестому входам блока анализа синдрома, второй — пятый и шестой выходы которого подключены соответственно к пятому— восьмому входам коммутатора и вторым входам блока управления, седьмой выход которого является тактовым выходом устройства, а восьмой выход подключен к третьему входу первого блока деления и тактовым входам первого и второго буферных регистров и первого — третьего элементов памяти, выходы второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ подключены к информационным входам первого элемента памяти, вторые входы первого — .етвертого элементов ИСКЛЮЧАЮЩЕЕ ИЛИ подключены соответственно к первым — четвертым выходам коммутатора, 2, Устройство поп.1, отл и ч а ю щее: с я тем, что блок управления содержит первый, второй и третий элементы И, триггер, первый и второй инверторы, дешифратор, элемент И вЂ” НЕ, первый и второй коммутаторы, первый и второй элементы задержки, первый и второй элементы ИЛИ, первый и второй счетчики импульсов, формирователь

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

1662010

1662010

1662010

Редактор Н. Рогулич

Заказ 2137 Тираж 461 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб„4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

&да

В

Ю

1 2 Я

Puz,f

Составитель 0, Тюрина

Техред М.Моргентал Корректор А, Осауленко