Устройство декодирования для исправления многократных стираний

(12) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЕКОДИРОВАНИЯ ДЛЯ ИСПРАВЛЕНИЯ МНОГОКРАТНЫХ СТИРАНИЙ(72) Авторы Фам Хак Хоан Конопелько(71) Заявитель Учреждение образования (73) Патентообладатель Учреждение обраБелорусский государственный унизования Белорусский государственверситет информатики и радиоэлекный университет информатики и троникирадиоэлектроники(57) Устройство декодирования для исправления многократных стираний, содержащее блок вычисления синдрома, регистр адресов стираний, ПЗУ синдромов, блок вычисления вектора согласования стираний, блок элементов И, блок формирования одиночных векторов несогласованных стираний, блок элементов ИЛИ и корректор, причем входы блока вычисления синдрома и первые входы корректора соединены и наряду с входами регистра адресов стираний являются входами устройства, выходы регистра адресов стираний соединены с входами ПЗУ синдромов и первыми входами блока элементов И, выходы которого соединены с входами блока формирования одиночных векторов несогласованных стираний, выходы этого блока соединены с входами блока элементов ИЛИ, выходы которого соединены со вторыми входами корректора, выходы корректора являются выходами устройства, отличающееся тем, что в устройство введен блок вычисления векторов согласования стираний, первые и вторые входы которого соединены соответственно с выходами блока вычисления синдрома и с выходами ПЗУ синдромов, а выходы - со вторыми входами блока элементов И.(56) 1. Фам Хак Хоан, Конопелько В.К. Исправление стираний кодами, исправляющими ошибки // Доклады БГУИР. - 2006. -6. - С. 19-22. 2. Блейхут. Теория и практика кодов, контролирующих ошибки. - М. Мир, 1986. 3. Конопелько В.К., Лосев В.В. Надежное хранение информации в полупроводниковых запоминающих устройствах. - М. Радио и связь, 1986. Полезная модель относится к вычислительной технике и может быть использована в системах передачи и хранения информации, в частности в оптических, магнитных запоминающих устройствах для защиты их от отказов и помех. Целью полезной модели является повышение быстродействия устройства исправления многократных стираний. Указанная цель достигается вычислением значения синдрома только один раз и сравнением его с всевозможными суммами синдромов одиночных ошибок, соответствующих стертым разрядам. Во многих системах передачи и хранения информации появляются стирания, которыми являются искаженные символы с их известной позицией. Наличие дополнительной информации о местонахождении стертых разрядов позволяет в два раза эффективнее использовать корректирующие возможности кодов 1. Известная переборная процедура исправления стираний, основанная на замене значений стертых разрядов всеми возможными комбинациями, вычислении синдромов и сравнении вычисленных синдромов с нулем, требует больших временных затрат. Поэтому устройство исправления стираний, построенное на основании данной процедуры, имеет низкое быстродействие. Другая известная процедура исправления ошибок и стираний связана с итеративным алгоритмом (чаще всего алгоритмом Берлекэмпа-Месси декодирования БЧХ икодов), основанным на модификации стандартного алгоритма исправления ошибок. Декодер по данному методу декодирования обладает низким быстродействием из-за решения ключевого уравнения над полем Галуа 2. Наиболее близким к предлагаемой полезной модели является декодер для исправления ошибок из-за отказов в памяти, содержащий счетный регистр, блок приоритета, ПЗУ синдромов, блок анализа частных сумм, блок нахождения вектора несогласованных ошибок, корректирующие сумматоры по модулю два, причем на один из входов блока анализа частных сумм поступают частные синдромы о возможных одиночных ошибках хранения,а на другие входы - сигналы о полном синдроме с выходов блока вычисления синдрома,на одном из выходов блока анализа частных сумм появится единичный сигнал, соответствующий частной сумме, которая равна нулю. Однако данное устройство требует больших аппаратурных затрат на построение блока анализа частных сумм и блока нахождения вектора несогласованных ошибок при исправлении многократных стираний 3, с. 204, рис. 6.7. В техническом решении поставлена задача разработки устройства декодирования многократных стираний с высоким быстродействием. Техническим результатом, который может быть получен при использовании данной полезной модели, является декодер для исправления многократных стираний с высоким быстродействием и невысокой сложностью по сравнению с коррекцией многократных ошибок. Устройство декодирования для исправления многократных стираний, содержащее блок вычисления синдрома, регистр адресов стираний, ПЗУ синдромов, блок вычисления вектора согласования стираний, блок элементов И, блок формирования одиночных векторов несогласованных стираний, блок элементов ИЛИ и корректор, причем входы блока вычисления синдрома и первые входы корректора соединены и наряду с входами регистра адресов стираний являются входами устройства, выходы регистра адресов стираний соединены с входами ПЗУ синдромов и первыми входами блока элементов И, выходы которого соединены с входами блока формирования одиночных векторов несогласованных 2 39012007.10.30 стираний (БФОВНС), выходы этого блока соединены с входами блока элементов ИЛИ,выходы которого соединены со вторыми входами корректора, выходы корректора являются выходами устройства, отличающееся тем, что в устройство введен блок вычисления векторов согласования стираний, первые и вторые входы которого соединены соответственно с выходами блока вычисления синдрома и с выходами ПЗУ синдромов, а выходы со вторыми входами блока элементов И. Сущность данной полезной модели заключается в том, что предлагаемое устройство исправляет многократные стирания с высоким быстродействием за счет вычисления синдрома только один раз и введения в устройство блока вычисления вектора согласования стираний. Нахождение вектора согласования стираний осуществляется следующим образом. В соответствии с адресами стертых разрядов, хранимыми в регистре адресов стираний, вычисляются синдромы одиночных ошибок, хранимые в ПЗУ синдромов, которые,поступая в блок вычисления векторов согласования стираний, формируют в нем всевозможные суммы этих синдромов на сумматорах по модулю два. Далее эти суммы сравниваются с вычисленным синдромом в блоке вычисления синдрома. В результате на одном из выходов элементов сравнения установится единичный сигнал, по которому в блоке элементов ИЛИ сформируется вектор согласования стираний, являющийся выходом блока вычисления вектора согласования стираний. Предложение иллюстрируется следующими чертежами. На фиг. 1. представлена структурная схема устройства, на фиг. 2 - структурная схема блока вычисления вектора согласования стираний. Реализация блока вычисления синдрома, регистра адресов стираний, ПЗУ синдромов, дешифраторов, корректора известна. В этих блоках используются элементы И, ИЛИ, НЕ, сумматоры по модулю два. Устройство декодирования для исправления многократных стираний содержит блок вычисления синдрома 1, регистр адресов стираний 2, выходы 3 которого являются входами ПЗУ синдромов 4 и первыми входами блока элементов И 5, выходы 6 ПЗУ синдромов и выходы 7 блока вычисления синдрома соответственно являются вторыми и первыми входами блока вычисления вектора согласования стираний 8, выходы 9 которого соединены с вторыми входами блока элементов И, выходы 10 которого являются входами блока формирования одиночных векторов несогласованных стираний (БФОВНС) 11,выходы 12 которого являются входами блока элементов ИЛИ 13, выходы 14 которого и входы 15 являются входами корректора 16 и устройства, выходы 17 корректора являются выходами устройства (фиг. 1). Устройство работает следующим образом. Принятое кодовое слово поступает в блок вычисления синдрома 1, где вычисляется синдромпо принятым входным символам. Информация о адресах стертых символов хранится в регистре адресов стираний 2, а соответствующие им значения синдромов всех одиночных ошибок хранятся в ПЗУ синдромов 4. Сигналы с выходов ПЗУ синдромов и блока вычисления синдрома 1 поступают на вторые 6 и первые 7 входы блока вычисления вектора согласования стираний 8, на выходах 9 которого формируются векторы согласования стираний. Сигналы с выходов 9 блока вычисления вектора согласования стираний и регистра адресов стираний поступают на входы блока элементов И. На выходах 10 блока элементов И 5 сформируются только сигналы об адресах несогласованных стираний, которые, поступая в БФОВНС 11, установят на его выходах 12 единичные сигналы, соответствующие несогласованным позициям. В блоке элементов ИЛИ 13 произойдет объединение этих сигналов, в результате чего на выходах сформируется полный вектор несогласованных стираний, который скорректирует в корректоре ошибочные позиции в принятом слове. На фиг. 2 представлена структурная схема блока вычисления вектора согласования стираний, содержащего блок формирования множеств 18, блок сравнения 19, блок элементов ИЛИ 20. Данный блок работает следующим образом. Синдромы одиночных стираний из выходов 6 ПЗУ синдромов поступают на входы блока формирования мно 3 39012007.10.30 жеств 18, состоящего из сумматоров по модулю два. Выходы 21 блока формирования множествпоступают на первые входы блока сравнения 19, а на второй вход поступает вычисленный синдромс выходов 7 блока вычисления синдрома. Блок сравнения опре деляет совпадение -разрядных сигналов на его двух входах, при этом на одном из выходов 22 блока сравнения появится единичный сигнал, который поступает в соответствующие элементы ИЛИ блока элементов ИЛИ 20, и на его выходах 9 появится вектор согласования стираний. Например, при условии, что четвертый из выходов 21 совпадает с входами 6, на четвертом выходе блока сравнения появится единичный сигнал, который поступает в первый и второй элементы ИЛИ, что обеспечит выдачу единичных сигналов на первом и втором выходах 9. Технико-экономическое преимущество предложенного устройства декодирования для исправления многократных стираний по сравнению с известными устройствами на основе переборного метода заключается в повышении быстродействия за счет уменьшения задержек при вычислении синдрома. Это объясняется тем, что известные устройства должны вычислить синдромы много раз, и каждый раз необходимо вычислить синдром по подставляемым значениям стираний и правильным значениям нестертых символов. Кроме того, сложность вычислений суммирования и сравнения -разрядных чисел, которая пропорциональна 21 , где- число исправляемых стираний, и независима от длины слова ,значительно меньше сложности селекторапри коррекции того же числа ошибок 0, особенно при большой длине слова. Например, при 4 и длине кода 63 сложность устройства исправления 4-х стираний примерно в 20000 раз меньше сложности селектора при коррекции 4-х ошибок. Таким образом, предложенное устройство обладает высоким быстродействием и невысокой сложностью по сравнению с коррекцией многократных ошибок. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 4