Устройство декодирования для коррекции двойных ошибок

ГОСУДАРСТВЕННЫЙ ПАТЕНТНЫЙ КОМИТЕТ РЕСПУБЛИКИ БЕЛАРУСЬ УСТРОЙСТВО ДЕКОДИРОВАНИЯ ДЛЯ КОРРЕКЦИИ ДВОЙНЫХ ОШИБОК(71) Заявитель Белорусский государственный университет информатики и радиоэлектроники(73) Патентообладатель Белорусский государственный университет информатики и радиоэлектроники(57) Устройство декодирования для коррекции двойных ошибок, содержащее блок вычисления синдрома,первый и второй дешифраторы указания степени элементов поля, блок корректирующих сумматоров по модулю два, первый и второй селекторы указания начального и текущего местоположения ошибок, причем входы блока вычисления синдрома и первые входы блока корректирующих сумматоров по модулю два объединены, первые и вторые выходы блока вычисления синдрома соединены соответственно с входами первого и второго дешифраторов указания степени элементов поля, выходы первого дешифратора указания степени элементов поля соединены с соответствующими объединенными первыми входами первого и второго селекторов указания начального и текущего местоположения ошибок, выходы второго дешифратора указания степени элементов поля соединены с соответствующими вторыми входами первого селектора указания начального местоположения ошибок, выходы которого соединены с соответствующими вторыми входами второго селектора указания текущего местоположения ошибок, отличающееся тем, что в устройство введены блок анализа синдрома, блок анализа трехкратных ошибок, блок анализа четырехкратных ошибок, блок анализа ошибок в разряде контроля четности, блок формирования трехкратных ошибок, блок формирования четырехкратных ошибок, формирователь вектора ошибок, первый и второй блоки перестановки, входы первого блока перестановки являются контрольными и информационными входами устройства, а выходы соединены с объединенными входами блока вычисления синдрома и первыми входами блока корректирующих сумматоров по модулю два, третий выход блока вычисления синдрома соединен с первым входом блока анализа ошибок в разряде контроля Фиг. 1 четности, первым входом блока анализа трехкратных ошибок, первым входом блока анализа четырехкратных ошибок, первые и вторые входы блока анализа синдрома соединены соответственно с первыми и вторыми выходами блока вычисления синдрома, первый выход блока анализа синдрома соединен с первым входом блока формирования трехкратных ошибок и вторым входом блока анализа четырехкратных ошибок,выход которого соединен с первым входом блока формирования четырехкратных ошибок, выходы которого 3907 1 соединены с четвертыми входами формирователя вектора ошибок, второй выход блока анализа синдрома соединен со вторым входом блока анализа ошибок в разряде контроля четности и вторым входом блока анализа трехкратных ошибок, выход которого соединен со вторым входом блока формирования трехкратных ошибок, третий вход блока анализа трехкратных ошибок и третий вход блока анализа ошибок в разряде контроля четности соединены с соответствующим выходом первого селектора указания начального местоположения ошибок, выход блока анализа ошибок в разряде контроля четности соединен со вторым входом формирователя вектора ошибок, вторые входы блока формирования четырехкратных ошибок соединены с соответствующими выходами второго дешифратора указания степени элементов поля, выходы второго селекторов указания текущего местоположения ошибок соединены с первыми входами (формирователя вектора ошибок, третьи входы блока формирователя трехкратных ошибок соединены с объединенными первыми входами первого и второго селекторов указания начального и текущего местоположения ошибок, выходы блока формирования трехкратных ошибок соединены с третьими входами формирователя вектора ошибок,выходы которого соединены со вторыми входами блока корректирующих сумматоров по модулю два, выходы которого соединены с входами второго блока перестановки, выходы которого являются выходами устройства.(56)1833968 1, 1993. Давыдов А.А., Дрожжина-Лобинская А.Ю., Калинчева В.В. Реализация на БИС параллельного декодера кодов БЧХ, исправляющих двойные независимые ошибки и байты ошибок длины четыре. - В сб. Вопросы кибернетики Вып. 145. Базовое программное обеспечение суперЭВМ / Под ред. В.А. Мельникова, Ю.Г. Давыдова. - М. АН СССР. Научн. совет по комплекс. пробл. Кибернетика. - 1990. - С. 151-174. Изобретение относится к области вычислительной техники, в частности к устройствам контроля запоминающих устройств и может быть использовано для повышения надежности запоминающих устройств. Известно устройство декодирования кодов Боуза-Чоудхури-Хоквингейма (БЧХ), содержащее вычислитель синдрома, блок обнаружения трехкратных ошибок, формирователи, дешифраторы и корректор, позволяющее корректировать двойные и модульные ошибки (длина модуля 4). Однако подобное устройство характеризуется невысоким быстродействием из-за сложности блока коррекции 1. Наиболее близким к предлагаемому изобретению является устройство декодирования для коррекции двойных ошибок с высоким быстродействием, содержащее блок вычисления синдрома, первый и второй дешифраторы указания степени элементов поля, блок корректирующих сумматоров по модулю два, первый и второй селекторы указания начального и текущего местоположения ошибок, причем входы блока вычисления синдрома и первые входы блока корректирующих сумматоров по модулю два объединены и являются информационными и контрольными входами устройства, выходы блока корректирующих сумматоров по модулю два являются выходами устройства, первые и вторые выходы блока вычисления синдрома соединены соответственно с входами первого и второго дешифраторов указания степени элементов поля, выходы первого дешифратора указания степени элементов поля соединены с соответствующими объединенными первыми входами первого и второго селекторов указания начального и текущего местоположения ошибок,выходы второго дешифратора указания степени элементов поля соединены с соответствующими вторыми входами первого селектора указания начального местоположения ошибок, выходы которого соединены с соответствующими вторыми входами второго селектора указания текущего местоположения ошибок, выходы которого соединены с соответствующими входами блока корректирующих сумматоров по модулю два 2. Однако данное устройство не позволяет корректировать модульные ошибки. Задачей данного изобретения является расширение функциональных возможностей устройства декодирования за счет коррекции не только двойных, но и модульных ошибок с высоким быстродействием. Решение поставленной задачи достигается тем, что устройство декодирования для коррекции двойных ошибок, содержащее блок вычисления синдрома, первый и второй дешифраторы указания степени элементов поля, блок корректирующих сумматоров по модулю два, первый и второй селекторы указания начального и текущего местоположения ошибок, причем входы блока вычисления синдрома и первые входы блока корректирующих сумматоров по модулю два объединены, первые и вторые выходы блока вычисления синдрома соединены соответственно с входами первого и второго дешифраторов указания степени элементов поля, выходы первого дешифратора указания степени элементов поля соединены с соответствующими объединенными первыми входами первого и второго селекторов указания начального и текущего местоположения ошибок, выходы второго дешифратора указания степени элементов поля соединены с соответствующими вторыми входами селектора указания начального местоположения ошибок, выходы которого соединены с соответствующими вторыми входами второго селектора указания текущего местоположения ошибок, дополнительно содержит блок анализа синдрома, блок анализа трехкратных ошибок, блок анализа четырехкратных ошибок, блок анализа ошибок в разряде контроля четности, блок формирования трехкратных оши 2 3907 1 бок, блок формирования четырехкратных ошибок, формирователь вектора ошибок, первый и второй блоки перестановки, входы первого блока перестановки являются контрольными и информационными входами устройства, а входы соединены с объединенными входами блока вычисления синдрома и первыми входами блока корректирующих сумматоров по модулю два, третий выход блока вычисления синдрома соединены с первым входом блока ошибок в разряде контроля четности, первым входом блока анализа трехкратных ошибок, первым входом блока анализа четырехкратных ошибок, первые и вторые входы блока анализа синдрома соединены соответственно с первыми и вторыми выходами блока вычисления синдрома, первый выход блока анализа синдрома соединены с первым входом блока формирования трехкратных ошибок и вторым входом блока анализа четырехкратных ошибок, выход которого соединен с первым входом блока формирования четырехкратных ошибок, выходы которого соединены с четвертыми входами формирователя вектора ошибок, второй выход блока анализа синдрома соединен со вторым входом блока анализа ошибок в разряде контроля четности и вторым входом блока анализа трехкратных ошибок, выход которого соединен со вторым входом блока формирования трехкратных ошибок, третий вход блока анализа трехкратных ошибок и третий вход блока ошибок в разряде контроля четности соединены с соответствующим выходом первого селектора указания начального местоположения ошибок, выход блока анализа ошибок в разряде контроля четности соединен со вторым входом формирователя вектора ошибок, вторые входы блока формирования четырехкратных ошибок соединены с соответствующими выходами второго дешифратора указания степени элементов поля, выходы второго селектора указания текущего местоположения ошибок соединены с первыми входами формирователя вектора ошибок, третьи входы блока формирования трехкратных ошибок соединены с объединенными первыми входами первого и второго селекторов указания начального и текущего местоположения ошибок, выходы блока формирования трехкратных ошибок соединены с третьими входами формирователя вектора ошибок, выходы которого соединены со вторыми входами блока корректирующих сумматоров по модулю два, выходы которого соединены с входами второго блока перестановки, выходы которого являются выходами устройства. Сущность данного изобретения заключается в том, что предлагаемое устройство корректирует не только одиночные и двойные, но и модульные ошибки с высоким быстродействием за счет применения специальной обработки стандартной проверочной матрицы БЧХ-кода и введения в устройство блока анализа синдрома, блока анализа трехкратных ошибок, блока анализа четырехкратных ошибок, блока анализа ошибок в разряде контроля четности, блока формирования трехкратных ошибок, блока формирования четырехкратных ошибок, формирователя вектора ошибок, первого и второго блоков перестановки и новых связей. Предложение иллюстрируется следующими чертежами. На фиг. 1 представлена проверочная матрица Н модифицированного БЧХ-кода с кодовым расстоянием 6, на фиг. 2 - проверочная матрица БЧХ-кода с 6, на фиг. 3 - блок-схема устройства, на фиг. 4 - первый блок перестановки, на фиг. 5 - второй блок перестановки, на фиг. 6 - блок анализа синдрома, на фиг. 7 - блок анализа ошибок в разряде контроля четности,на фиг. 8 - блок анализа трехкратных ошибок, на фиг. 9 - блок анализа четырехкратных ошибок, на фиг. 10 блок формирования трехкратных ошибок, на фиг. 11 - блок формирования четырехкратных ошибок, на фиг. 12 - формирователь вектора ошибок в таблице приведены значения ошибочных разрядов, соответствующих им элементов поля синдромов, значения параметраи разряда контроля четности для одиночных и двойных ошибок, а также для всех возможных значений ошибочных разрядов для каждого модуля (длина модуля 4). Устройство декодирования для коррекции двойных и модульных ошибок содержит первый блок перестановки 1, входы 2 которого соединены с контрольными и информационными входами устройства, выходы 3 блока перестановки соединения с объединенными входами блока вычисления синдрома 4 и первыми входами блока корректирующих сумматоров по модулю два 5, первые 6 выходы блока вычисления синдрома соединены с первыми входами блока анализа синдрома 7 и входами первого дешифратора указания степени элементов поля 8, вторые выходы 9 блока вычисления синдрома соединены со вторыми входами блока анализа синдрома и входами второго дешифратора указания степени элементов поля 10, третий выход 11 блока вычисления синдрома соединен с первым входом блока анализа ошибок в разряде контроля четности 12,первым входом блока анализа трехкратных ошибок 13 и первым входом блока анализа четырехкратных ошибок 14, первый выход 15 блока анализа синдрома соединен с первым входом блока формирования трехкратных ошибок 16 и вторым входом блока анализа четырехкратных ошибок, второй выход 17 блока анализа синдрома соединен со вторым входом блока анализа ошибок в разряде контроля четности и вторым входом блока анализа трехкратных ошибок, выходы 18 первого дешифратора указания степени элементов поля соединены с объединенными первыми входами первого 19 и второго 20 селекторов указания начального и текущего местоположения ошибок и третьим входами блока формирования трехкратных ошибок, выходы 21 второго дешифратора указания степени элементов поля соединены со вторыми входами первого селектора указания начального местоположения ошибок и вторыми входами блока формирования четырехкратных ошибок 22, выходы 23 первого селектора указания начального местоположения ошибок соединены со вторыми входами селектора указания текущего местоположения ошибок, выходы 24 которого соединены с первыми входами формирователя вектора ошибок 25, третий вход блока анализа ошибок в разряде контроля 3 3907 1 четности и третий вход блока анализа трехкратных ошибок соединены с соответствующим выходом первого селектора указания начального местоположения ошибок, выход 26 блока анализа ошибок в разряде контроля четности соединен со вторым входом формирователя вектора ошибок, выход 27 блока анализа трехкратных ошибок соединен со вторым входом блока формирования трехкратных ошибок, выходы 28 которого соединены с третьими входами формирователя вектора ошибок, выход 29 блока анализа четырехкратных ошибок соединен с первым входом блока формирования четырехкратных ошибок, выходы 30 которого соединены с четвертыми входами формирователя вектора ошибок, выходы 31 которого соединены со вторыми входами блока корректирующих сумматоров, выходы 32 которого соединены с входами второго блока перестановки 33, выходы 34 которого являются выходами устройства. В предложенном устройстве используется проверочная матрица Н модифицированного БЧХ-кода, построенная по итеративному методу 1. На фиг. 1 в качестве примера конкретного исполнения для кода длины 32 представлена проверочная матрица Н (32, 21) с кодовым расстоянием 6. Эта матрица отличается от проверочной матрицы Н БЧХ-кода с 6 (см. фиг. 2) порядком следования разрядов. При появлении ошибок значения синдрома(1, 2, ч)(р, , ч), где р и- верхние и нижние значения столбцов проверочной матрицы, ч - разряд контроля четности. Как видно из таблицы, значения(1, 2, ч) для всех возможных сочетаний модульной ошибки длины 4 не пересекаются со значениями синдрома одиночных и двойных ошибок. Причем если ч 0 и 1(000), то имеет место сплошной байт ошибок в этом случае номер ошибочного модуля можно определить по значению 2. Если ч 1, значение параметра(определяющего класс двойных ошибок для БЧХкода) отлично от нуля и хотя бы одно из значений 1 и 2 отлично от нуля, произошла модульная ошибка веса три ошибочные разряды можно определить по значениям 1 или 2 (в случае равенства 1 нулю). Как известно, все сочетания 2-1231465 двойных ошибок можно разбить на 2-1/ (-1)15 классов 2, приведенных в таблице. Например, если ошибки произошли во втором и третьем разрядах, то им соответствует синдром(20, 4, 0) и значения 6. Для всех 15 классов двойных ошибок 0, ч 0. Первая строка в классах определяет начальное местоположение вектора ошибок, остальные - текущие. Каждый класс ошибок определяется соответствующим значением параметра 0, ч 0. Первая строка в классах определяет начальное местоположение вектора ошибок, остальные - текущие. Каждый класс ошибок определяется соответствующим значением параметра- 3 р. Отсюда следует, что зная , а следовательно,начальное значение вектора ошибок Е 0 и соответствующее ему р 0, фактическое текущее значение Е можно определить по сдвигу (р-р 0). Если произошла двойная ошибка, причем одним из ошибочных разрядов является разряд контроля четности, то ч 0, но при этом значение 0. В случае одиночной ошибки в одном из разрядов кодового слова (за исключением разряда контроля четности),0, 10, 20, но ч 1. Если же ошибка произошла только в разряде контроля четности, значение синдрома(0,0,1). Устройство работает следующим образом. Кодовое слово модифицированного БЧХ-кода, задаваемого матрицей Н (фиг. 1), поступает на входы 2 блока перестановки 1, на выходе которого - кодовое слово с разрядами, переупорядоченными согласно проверочной матрицы Н БЧХ-кода с 6 (фиг. 2). Данная перестановка разрядов кодового слова позволяет корректировать двойные ошибки по методу, основанному на таблице смежных классов, обеспечивающим коррекцию двойных ошибок с высоким быстродействием 2. Переупорядоченное кодовое слово поступает на входы 3 блока вычисления синдрома. На выходах 6 и 9 блока 4 формируется значения синдрома 1 р и 2, которые поступают соответственно на входы первого 8 и второго 10 дешифраторов указания степени элементов поля . Например, если на входы дешифратора поступает сигнал об элементе 20, то на двадцатом выходе дешифратора появляется единичный сигнал. Значения синдрома р ис выходов 6 и 9 поступают также на входы блока анализа синдрома 7, на первом выходе 15 которого нулевой сигнал появляется только в случае 10 единичный сигнал на втором выходе блока 7 показывает, что хотя бы одно из значений 1 или 2 отлично от нуля. Сигналы с третьего выхода 11 блока вычисления синдрома и первого выхода 15 блока анализа ошибок поступают на входы блока анализа четырехкратных ошибок 14, на выходе 29 которого в случае равенства ч и 1 нулю (то есть в случае модульной ошибки веса четыре) появляется единичный сигнал, который поступает на первый вход блока формирования четырехкратных ошибок 22. Поскольку в случае модульной ошибки веса четыре 10, номер ошибочного модуля, а следовательно номера ошибочных разрядов, можно определить по степени элемента . Поэтому на вторые входы блока 22 поступают сигналы с 19, 4, 25, 8, 23,30, 2 и 16 выходных шин 21 второго дешифратора 10. В результате на выходах 30 блока формирования четырехкратных ошибок 22, соответствующих четырем ошибочным разрядам появятся единичные сигналы. Например, если на первом входе блока 22, и на четвертой выходной шине второго дешифратора 10 - единичные сигналы, имеет место ошибка веса четыре в первом модуле соответствующих четырем ошибочным разрядам появляется единичные сигналы. Например, если на первом входе блока 22 и на четвертой выходной шине второго дешифратора 10 - единичные сигналы, имеет место ошибка веса четыре в первом модуле 4 3907 1 в этом случае единичные сигналы появятся на 2, 5, 6 и 27 выходных шинах блоков формирования четырехкратных ошибок. При появлении модульной ошибки веса три единичные сигналы поступают на первый (ч 1) и второй(хотя бы одно из значений 1 или 2 отлично от нуля) входы блока анализа трехкратных ошибок 13, на третьем входе которого - нулевой сигнал (который свидетельствует о неравенственулю), поступающий с шины соответствующей нулевому значению параметра . В результате на выходе блока 13 появляется единичный сигнал, который поступает на второй вход блока формирования трехкратных ошибок 16. Единичный сигнал на одном из выходов первого дешифратора указания степени элементов поля 8 поступает на третьи входы блока 16 в результате на трех из 33 выходов 28 появятся сигналы, указывающие на ошибочные разряды. Например, при ошибке в пятом модуле, причем ошибочные разряды - 21, 24, 25, синдром(15, 23,1),9 на первом и втором входах блока 13 появляются единичные сигналы (чи 10, 20), на третьем входе блока 13 - нулевой сигнал (0) в результате на выходе 27 блока анализа трехкратных ошибок появится единичный сигнал. Данный сигнал поступает на второй вход блока формирования трехкратных ошибок 27, на третьи входы которого поступает единичный сигнал с пятнадцатого выхода первого дешифратора 8. При этом единичные сигналы появляются на 21, 24 и 25 выходах блока 16. Как видно из таблицы, при появлении ошибки веса три возможно равенство 1 нулю (ошибка в разрядах(0, 1, 18) нулевого модуля). Поэтому на первый вход блока формирования трехкратных ошибок 16 поступает сигнал с первого 15 выхода блока анализа синдрома 7 о равенстве 1 нулю. При нулевом сигнале на первом входе и единичном сигнале на втором входе блока 16, характеризующим ошибку в разрядах 0, 1, 18, единичные сигналы появятся на нулевом, первом и восемнадцатом его выходах. Если произошла двойная ошибка в разрядах 0, 30, единичные сигналы на одних из выходов 6 и 9 поступают на входы селектора 19 в результате на одном из выходов 23 появится единичный сигнал, указывающий на соответствующее . Например, при ошибках во втором и четвертом разрядах синдром равен(7,2, 0) тогда на седьмом выходе дешифратора 8 и втором выходе дешифратора 10 появятся единичные сигналы, которые откроют соответствующий элемент И на пересечении шин первого селектора 19 в результате на одном из выходов 23, соответствующем значению 12, появится единичный сигнал. Данный сигнал поступает на вторые входы второго селектора 20 в соответствии с разбивкой на классы. То есть, шина соответствующая 0 (нулевая шина выходов первого селектора 19) соединена с нулевой вертикальной шиной селектора 20, шина с 6 - с 13 и 14 шинами, шина с 12 - с 26 и 28 шинами и т.д. Это следует непосредственно из приведенной таблицы. На первые входы второго селектора 20 поступает сигнал о текущем значении р, по которому происходит сдвиг начального состояния вектора ошибок. Так, например, при единичных сигналах на шинах 12 и р 5, на выходах 24 селектора 20 появляются сигналы, указывающие на местоположение ошибок в слове в нулевом и втором разрядах при 12 и р 7 - втором и четвертом разрядах. В случае, когда значениедля класса двойных ошибок совпадает со значениемдля модульной ошибки веса три, единичные сигналы появляются и на соответствующих выходах 24 блока 20, указывающих на двойную ошибку, и на соответствующих выходах 28 блока 16, указывающих на модульную ошибку веса три. В этом случае различие двойных и модульных ошибок осуществляется в формирователе 25 по сигналу о кратности данной ошибки, поступающему на 32 шину третьих входов блока 25. При одиночной ошибке (кроме ошибки в разряде контроля четности), а также в случае двойной ошибки,когда одним из ошибочных разрядов является контроль четности,0. В этом случае опрашивается нулевая вертикальная шина селектора 20 и вектор ошибок с выходов 18 дешифратора 8 поступает без изменения на выходы 24 селектора 20. Тем самым в блоке 5 происходит коррекция ошибок в соответствующем разряде(с 0 по 30). Сигнал о наличии ошибки в разряде контроля четности поступает на соответствующий вход блока с выхода 26 блока анализа ошибок в разряде контроля четности 12. Единичный сигнал на выходе блока 12 появляется либо в случае 10, 20, ч 1 (на выходе 17 блока 7 нулевой сигнал одиночная ошибка в разряде контроля четности), либо в случае ч 0,0 (единичный сигнал на нулевой шине выходов 23 первого селектора 19 двойная ошибка, причем один из ошибочных разрядов - разряд контроля четности). Это следует из приведенной таблицы. В блоке 5 происходит коррекция информации, поступающей на входы 3 блока вычисления синдрома,сигналами, отображающими вектор ошибок с выходов 31 формирователя 25. Скорректированная информация поступает с выходов 32 блока 5 на вход второго блока перестановки 33, на выходе которого - информация, соответствующая матрице Н модифицированного БЧХ-кода (фиг. 1). 3907 1 Источники информации 1.1833968 Ф 1, 1993. 2. Давыдов А.А., Дрожжина-Лабинская А.Ю., Калинчева В.В. Реализация на БИС параллельного декодера кодов БЧХ, исправляющих двойные независимые ошибки и байты ошибок длины четыре. - В сб. Вопросы кибернетики. Вып. 145 Базовое программное обеспечение суперЭВМ / Под ред. В.А. Мельникова, Ю.Г. Давыдова. - Москва АН СССР, Научн. совет по комплекс. пробл. Кибернетика, 1990. - С. 151-174. Государственный патентный комитет Республики Беларусь. 220072, г. Минск, проспект Ф. Скорины, 66.