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

СОЮЗ СОВЕТСКИХСОЦИАЛ ИСТИЧ Е С КИХРЕСПУБЛИК 2010 9) Ы 2)5 Н 03 М 13/00 ЕТЕН ОПИСА ИЗО АВТОРСКОМУ С ТЕЛ ЬСТВ ническии институт ия и практика кодо бки. - М.: Мир, 198. 6. 2 2. ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(54) УСТРОЙСТВО КОРРЕКЦИИ ДВОЙНЫХОШИБОК С ИСПОЛЬЗОВАНИЕМ КОДА РИДА-СОЛОМОНА(57) Изобретение относится к вычислительной технике, а именно к устройствам контроля запоминающих устройств, и может быть использовано для повышения достоверности информации, хранимой в запоминающих устройствах. Целью изобретения является повышение быстродействия уст-. ройства, Устройство содержит блок 1 деления, буферный регистр 2, блок 3 управления, блок 4 деления, блок 5 совпадения, блок 6 анализа синдрома, коммутатор 7, элементы ИСК)ЮЧАЮЩЕЕ ИЛИ 8 - 11, буферный регистр 12. элементы 13 - 15 памяти, 1 э.п, флы, 6 ил.Изобретение относится к вычислительной технике, а именно к устройствам контроля запоминающих устройств, и может быть использовано для повышения достоверности информации, хранимой в запоминающих устройствах. 10 15 20 25 30 35 40 45 9(х) = (х -гг= ) = (х -а) (х -а(х -аз) х х (х-а), (1) для исправления двукратных ошибок, где с - кратность ошибки. Для лучшего понимания работы устройства необходимо отметить, что в его основу положен конвеерный вариант устройства коррекции Меггита с вылавливанием ошибок и символы кодового слова принадлежат полю Галуа 6 Р(2 ). Целью изобретения является повышение быстродействия устройства,На фиг,1 представлена блок-схема устройства коррекции двойных ошибок с использованием кода Рида-Соломона; нафиг.2 - функциональная схема блока управления; на фиг.3 - эпюры напряжений навыходах некоторых элементов блока управления; на фиг,4 - функциональная схемаблока деления; на фиг.5 - функциональнаясхема блока анализа синдрома; на фиг.б -функциональная схема коммутатора,Устройство содержит блок 1 деления,буферный регистр 2, блок 3 управления,блок 4 деления, блок 5 совпадения, блок банализа синдрома, коммутатор 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 по модулю два.Устройство работает следующим образом,В устройстве исследуется полиномиальное представление порождающего полинома кода Рида-СоломонаС информационных входов декодируемое кодовое слово посимвольно заносится в буферный регистр 2 и блок 1 деления, где за время, равное числу тактов, определяемому числом символов кодового слова, вычисляется синдром. После поступления последнего символа принимаемого слова вычисленный синдром перезаписывается в блок 4 деления, а очередное кодовое слово поступает в блок деления и в буферный регистр 2, информация с которого синхронно с поступлением символов нового кодового слова перезаписываетсяв буферный 50 55 синдрома выдает сигналы на входы коммутатора 7, приводящие к одновременному отпиранию двух каналов, при двукратной ошибке в соответствии с местоположением отличных от нуля коэффициентов синдрома. При этом каналы коммутатора 7 соединяют выходы второго блока 4 деления так, чтобы а 1 поступал на элемент 8, а 2 - на элемент 11, аз - на элемент 10, а 4 - на элемент 9, на другие входы которых поступают соответствующие символы кодового слова, подлежарегистр 12, К выходам блока 4 деления подключен блок 6 анализа синхрома, контролирующий состояние разрядов синдрома и вырабатывающий при определенном значении управляющие сигналы. При обнаружении им в одной из декодируемых комбинаций синдрома одно или двукратных ошибок соответственно вида а 400 а 1, ОазОа 1 00 а а 1, 000 а 1, где а 1, а 2, аз, а 4 - коэффициенты, на которые корректируются соответствующие символы кодового слова, на выходах устанавливаются управляющие сигналы, Один из них, поступая на второй вход блока 5 совпадения, открывает его и соответствующий коэффициент, стоящий в последней, счет слева направо, ячейке второго блока 4 деления, поступает обратно, где происходит их взаимное вычитание. Одновременно с этим по другому управляющему сигналу отпирается канал коммутатора 7. и этот же коэффициент поступает на первые входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 8, а на вторые входы приходят перезаписываемые символы декодируемого слова и происходит исправление первой ошибки. Аналогичен процесс декодирования, если есть и вторые ошибки, Однако порядок коррекции ошибок изменяется, если декодируемая комбинация синдрома вычислена, а также, начиная с (2 п - г+ 1), где и - количество символов в слове; г - число проверочных символов и г = 2 с и за время, оставшееся до конца цикла, кратного и, вторая ошибка не успевает быть исправлена вышеизложенным способом, Блок 3 управления вырабатывает сигнал, по которому блок б анализаьщие декодированию, После исправления ошибок, если таковые были, по команде с блока 3 управления блок б анализа синдрома отключается и оставшиеся в буферном регистре 12 символы поступают на выход,Рассмотрим функциональное назначение каждого из блоков устройства, блок 1 деления предназначен для деления последовательно поступающих символов кодового слова на порождающий полином кода Рида-Соломона, результатом чего является синдром принятого слова. Построение цепи деления приведено в (1),Буферный регистр 2 обеспечивает посимвольный прием и хранение поступающей информации.Блок 3 управления предназначен для выработки служебных сигналов, необходимых для работы устройства и обеспечивает; первоначальную установку в нулевое состояние блока 1 деления, блока 4 деления и своих внутренних элементов; импульсы синхронизации для работы всего устройства и внешнего источника информации; сигналы перезаписи из блока 1 деления в блок 4 деления; сигналы блокировки некоторых элементов до такта (2 п - г) и перевода в неактивное состояние в такте от (2 п - г+ 1), если ошибки обнаружены и исправлены, блоком б анализа синдрома, Сформированный отрицательный импульс необходим для установки в начальное состояние элементов блока 4 деления и через элемент И 18 элементов блока 1 деления, счетчик 19 импульсов, триггер 20. После этого прямоугольные импульсы с тактового генератора 21 поступают на выход блока 3 управления и всего устройства, а также на счетчик 19, который обеспечивает подсчет числа импульсов, соответствующих числу символов декодируемого кодового слова. Кроме того, импульсы подаются на вход элемента 22 задержки, обеспечивающий задержку сигнала на время, равное времени установления очередного состояния на выходе счетчика 19 Такой режим обеспечивает одновременное установление внутренних элементов блока 3 управления, зависящее от состояния счетчика 19 и поступление тактовых импульсов. С выхода элемента 22 задержки сигнал поступает на тактовые входы буферных регистров 2 и 12 блока 1 деления и на вход инвертора 23, инвертирующего тактовые импульсы, Прямые и инверсные тактовые импульсы поступают на соответствующие входы коммутатора 24, управление по каналам сигналов которого осуществляется соответственно инверсным и прямым управляющими сигналами, Инверсный управ 5 10 152025 30 3540455055 тактовым импульсом заносится в триггер 20 и блокирует работу блока 6 анализа синдрома. Такой режим необходим, чтобы исключить в оставшихся до 2 п тактах обнаружение ложных ошибок, обусловгенных тем, что с ляющий сигнал получается инвертированием прямого на инверторе 25, который приходит с элемента И 26, Последний обеспечивает состояние логического нуля на своем выходе сигналом низкого уровня, поступающим с выхода элемента И - НЕ 27, изменяющее свое состояние на противоположное только в момент установления на счетчике 19 состояния соответствующего последнему и такту, Такой режим работы управляющих сигналов коммутатора 24 обеспечивает формирование в отличие от других тактов двух импульсов синхронизации в одном и-м такте для блока 4 деления. По первому импульсу происходит обычнаяоперация деления, а по второму - перезапись состояния блока 1 деления в блок 4 деления, К выходам счетчика 19 подключен также дешифратор 28, обеспечивающий изменение выходного состояния из нуля в единицу, при установлении на выходе счетчика 19 соответствующих (2 п - г+ 1) такту. Единичный сигнал разрешает прохождение информации о наличии ошибки через элемент И 29, если таковая имеется, от блока 6 анализа синдрома, При этом необходимо наличие единичного сигнала на входе элемента И 29 с коммутатора 30, Коммутатор, начиная с (2 п - г+ 1) такта, сравнивает номер такта и вид синдрома, соответствующего декодируемой комбинации двукратной ошибки, если таковой определяется. Если число оставшихся тактов до 2 недостаточно для исправления двух ошибок последовательным способом, на выходе элемента И 29 устанавливается единица. Информация о номере такта поступает со счетчика 31, запускаемого сигналом с дешифратора 28, а импульсы счета - с тактового генератора 21,Данные о виде синдрома поступают на коммутатор ЗО с элементов ИЛИ 32 и ЗЗ, а также на прямую с блока 6 анализа синдрома. На каждый вход поступает информация о том синдроме, при котором ошибка уже последовательно исправлена быть не может. При этом вход соответствует определенному номеру такта и виду синдрома; первый - (2 п - -г+ 1) и адООа 1, второй с элемента ИЛИ 32 и (2 п - г+ 2) такту, третий - с элемента ИЛИ33 и (2 п - г + 3) такту. Элемент ИЛИ 32 анализирует информацию о синдромах вида адООа 1, ОазОа 1. элемент ИЛИ 33 - о синдромах вида а 400 а, ООа 2 а 1, ОазОа 1,Информация с выхода элемента И 29 (2 п - г - 2) или любым до 2 п включительно(2 п - г+ 1) такта коррекция синдрома в блоке 4 деления не производится, если ошибки исправляются одновременно, С выхода элемента И 26 сигналом логической единицы обеспечивается; переключение внутренних коммутаторов 43 блока 4 деления, необхо- димых при перезаписи синдромов; сброс в начальное состояние, через элемент 17 задержки и элемент. И 18, блока 1 деления,триггера 20, счетчика 19, Элемент 17 задержки задерживает импульс сброса в и-м такте, исходя из времени, необходимого длязавершения всех вычислительных операцийв устройстве,Блок 4 деления выполняет те же функции и выполнен по той же схеме, что и блок 1 деления, Отличительной особенностью является наличие внутренних коммутаторов 43. Они в и-м такте по сигналу с блока 3 управления переходят из режима сквозного канала в режим приема с внешнего устройства, по вторым входам, В данном случае это передача сигналов с выходов первого блока 1 деления на входы блока 4 деления для последующей записи и использования в качестве делимого.Блок 5 совпадения обеспечивает пропуск сигналов с соответствующей ячейки при обнаружении ошибки в блоке б анализа синдрома и поступлении соответствующего сигнала на второй вход схемы. Для этих целей можно использовать микросхемы 1533 КП 16, у которых по первым входам поступает сигнал, а вторые входы заземлены,Блок 6 анализа синдрома предназначен для обнаружения декодируемой комбинации синдрома, управления коммутатором 7 и блока.5 совпадения, выработке и передаче необходимых сигналов для блока 3 управления,блок 6 работает следующим образом, Сигналы, поступающие с первых, вторых, . третьих и четвертых выходов блока 4 деления, подаются на входы соответствующих элементов ИЛИ 35. Схемы определяют отличие от нуля значений этих сигналов соответствующих коэффициентам синдрома дешифратора 36 при наличии на его первых входах, с элементов ИЛИ 35, синдрома соответствующего вычисляемой комбинации двукратных ошибок, устанавливает на соответствующем выходе, подключенном к элементам И 37 - 39 или 40 нулевой сигнал, Определенный элемент И, где соответствие, а 400 а 1 - 40, ОазОа 1 - 39, 00 а 2 а 1 - 38, 000 а 1- 37, переключается в единичное состояние только при наличии единицы, поступающей с блока 3 управления в такте, начиная с 2 п - г + 1 на втором входе, Одновременно с этим, сигналы со всех выходов дешифрато 35 40 45 50 55 ра 36 поступают на выход блока и на входы элемента И - НЕ 41. На его выходе появляется сигнал логической единицы при наличии дешифрируемой комбинации ошибки, поступающей в блок 3 управления и в блок 5 совпадения, а также на второй вход элемента ИЛИ 42, Первый его вход соединен с выходом элемента И 37, Такое включение элемента ИЛИ 42 позволяет блоку б анализа синдрома как управлять соответствующим каналом коммутатора 7 при последовательном режиме исправления ошибок при обнаружении их в тактах до (2 п - г), так и работать в режиме одновременного исправления ошибок, используемом в тактах с (2 п - г+ 1). При обнаружении двукратной ошибки в тактах с (2 п - г + 1) на выходе элемента И 37 соответствующей а, аз или аг появляется логическая единица, одновременно с этим в единичное состояние переключается и элемент ИЛИ 42. Эти единичные уровни поступают на входы управления соответствующих каналов коммутатора 7 и открывают их,Коммутатор 7 обеспечивает прохождение сигналов, равных значению, на которое корректируется символ декодируемого слова, на соответствующие элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 8 - 11 в зависимости от вида синдрома.Предлагаемое устройство коррекции двойных ошибок с использованием кода Рида-Соломона по сравнению с известным повышает быстродействие конвейерных устройств коррекции за счет изменения процедуры коррекции, что позволяет на треть сократить время обработки каждого кодовОГО слова,Формула изобретения 1. Устройство коррекции двойных ошибок с использованием кода Рида-Соломона, содержащее первый блок деления, первые входы которого объединены с информационными входами первого буферного регистра и являются информационными входами устройства, первые - четвертые выходы первого блока деления подключены к одноименным входам второго блока деления, первые выходы которого подключены к первым входам блока совпадения, выходы первого буферного регистра подключены к первым входам первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы котороГо подключены к информационным входам, второго буферного регистра, выходы которого подключены к первым входам второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия устройства, в него введены блок управления, блок анализасиндрома.45 коммутатор и последовательно соединенные первый элемент памяти, третий элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, второй элемент памяти, четвертый элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и третий элемент памяти, выход которого является информационным выходом устройства, первый выход блока анализа синдрома подключен к первому входу блока управления и второму входу блока совпадения, выходы которого и первый выход блока управления подключены соответственно к пятым и шестому входам второго блока деления, вторые - . четвертые выходы которого подключены соответственно к первым - третьим входам блока анализа синдрома и коммутатора, четвертый вход которого объединен с четвертым входом блока анализа синдрома и подключен к первому выходу второго блока деления, второй - шестой выходы блока управления подключены соответственно к седьмому и восьмому входам второго блока деления, второму входу первого блока деления, пятому и шестому входам блока анализа синдрома, второй - пятый и шестой выходы которого подключены соответственно к пятому - восьмому входам коммутатора и вторым входам блока управления, седьмой выход которого является тактовым выходом устройства, а восьмой выход подключен к третьему входу первого блока деления и тактовым входам первого и второго буферных регистров и первого - третьего элементов памяти, выходы второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ подключены к информационным входам первого элемента памяти, вторые входы первого - етвертого элементов ИСКЛЮЧАЮЩЕЕ ИЛИ подключены соответственно к первым - четвертым выходам коммутатора,2, Устройство поп.1, отл и ч а ю щее: с я тем, что блок управления содержит первый, второй и третий элементы И, триггер, первый и второй инверторы, дешифратор, элемент И - НЕ, первый и второй коммутаторы, первый и второй элементы задержки, первый и второй элементы ИЛИ, первый и второй счетчики импульсов, формирователь 5 10 15 20 25 30 35 40 прямоугольного импульса и тактовый генератор, выход которого подключен к тактовым входам первого и второго счетчиков импульсов, входу первого элемента задержки и является седьмым выходом блока, выход формирователя прямоугольного импульса является вторым выходом блока и подключен к первому входу первого элемента И, выход которого является четвертым выходом блока и подключен к входам обнуления триггера, второго и первого счетчиков импульсов, выходы первого счетчика импульсов подключены к входам дешифратора и элемента И - НЕ, выход которого подключен к первому входу второго элемента И, выход первого элемента задержки подключен к тактовому входу триггера, первому входу первого коммутатора, входу первого инвертора и является восьмым выходом блока, выход первого инвертора подключен к вторым входам первого коммутатора и второго элемента И, выход которого является первым выходом устройства и подключен через второй элемент задержки к второму входу первого элемента И и непосредственно к третьему входу первого коммутатора и входу второго инвертора, выход которого подключен к четвертому входу первого коммутатора, выход которого является третьим выходом блока, выход дешифратора является шестым выходом блока и подключен к первому входу третьего элемента И и информационному входу второго счетчика импульсов, выходы которого подключены к адресным входам второго коммутатора, выход которого подключен к второму входу третьего элемента И, выход которого подключен к информационному входу триггера, выход которого является пятым выходом блока, выходы первого и второго элементов ИЛИ подключены соответственно к первому и второму информационным входам второго коммутатора,третий информационный вход которого и входы первого и второго элементов ИЛИ являются вторыми входами блока, третий вход третьего элемента И является первым входом блока.1662010 ктор А, Осауле едактор Н. Рогули Заказ 2137 Тираж 461 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина Родю бд