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

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО НОРМЕННОЙ КОРРЕКЦИИ ДВОЙНЫХ ОШИБОК(71) Заявитель Учреждение образования Белорусский государственный университет информатики и радиоэлектроники(72) Авторы Конопелько Валерий Константинович Смолякова Ольга Георгиевна Аль-алем Ахмед Саид(73) Патентообладатель Учреждение образования Белорусский государственный университет информатики и радиоэлектроники(57) Устройство норменной коррекции двойных ошибок, содержащее блок вычисления синдрома, выход которого является входом блока вычисления нормы, выход которого является входом устройства, отличающееся тем, что в устройство введены регистр циклического сдвига, генератор тактов, два триггера, счетчик сдвигов, селектор образующих норм, циклотомических классов, логический элемент ИЛИ, два постоянных запоминающих устройства ПЗУ 1 - ПЗУ 2, блок вычисления сдвига, блок определения вектора ошибки, причем один из выходов блока вычисления нормы соединен со входом регистра циклического сдвига, а второй - со входом блока вычисления сдвига, выход генератора тактов соединен со входами двух триггеров, выход первого их которых соединен с блоком определения вектора ошибки, а второго - со счетчиком сдвигов, селектором норм образующих циклотомических классов и регистром циклического сдвига, выход которого соединен со входом селектора образующих норм циклотомических классов, выходы которого подаются на блоки ПЗУ 1, ПЗУ 2 и логический элемент ИЛИ, выход которого соединен с разрешающим входом первого триггера, с запрещающим входом второго триггера и со счетчиком сдвигов, выход которого подается на соответствующие входы блоков ПЗУ 1, ПЗУ 2, выход ПЗУ 1 соединен со входом блока вычисления сдвига, выход которого соединен со входом блока определения вектора ошибки, с другим входом которого соединен выход блока ПЗУ 2, один из выходов блока определения ошибки соединен с запрещающим входом первого триггера, а второй является выходом устройства.(56) 1. Конопелько В.К., Липницкий В.А., Дворников В.Д. и др. Теория прикладного кодирования Учеб. пособие. В 2 т. Т. 2 / Под ред. проф. Конопелько В.К. - Минск БГУИР, 2004. 2. Конопелько В.К., Липницкий В.А. Теория норм синдромов и перестановочное декодирование помехоустойчивых кодов. - Минск БГУИР, 2000. 3. Липницкий В.А., Конопелько В.К. Норменное декодирование помехоустойчивых кодов и алгебраические уравнения. - Минск Изд. центр БГУ, 2007. Полезная модель относится к вычислительной технике и может быть использована в системах передачи и хранения информации, в частности в системах памяти для защиты от ошибок и сетях передачи данных. Синдромное декодирование, используемое для борьбы с ошибками, основано на таблице смежных классов. Поиск вектора ошибки осуществляется путем селектирования всех возможных комбинаций признаков ошибок (синдромов) и последующего определения вектора ошибок по синдрому. Известный алгоритм декодирования с использованием таблицы смежных классов, основанный на полном переборе и сравнении всех возможных синдромов с синдромом, вычисленным на основе принятого слова, требует больших временных затрат. Поэтому устройство декодирования, построенное на основании данной процедуры, имеет низкое быстродействие 1. Другая известная процедура, основанная на теории норм синдромов,связана с сокращением мощности множества синдромов, однако требует увеличения объема памяти, предназначенного для хранения норм синдромов. Декодер, построенный по данному методу декодирования, характеризуется большой аппаратурной сложностью 2. Наиболее близким к предлагаемой полезной модели является декодер, реализующий метод коррекции ошибок в двоичных кодах с использованием норм синдромов и имеющий ПЗУ для хранения кодов ошибок образующего вектора, содержащий блок вычисления синдрома, ПЗУ 1-5, два сумматора по модулю , блок вычисления месторасположения второй ошибки, два дешифратора, логический элемент ИЛИ и блок инвертирования,причем вход блока вычисления синдрома соединен со входом блока инвертирования, выходы блока вычисления синдрома соединены со входами ПЗУ 1-2, выходы которых подаются на входы первого сумматора по модулю , выход первого ПЗУ также подается на один из входов второго сумматора по модулю , выход второго сумматора по модулюсоединен со входом ПЗУ 3-5, выход одного из которых подается на второй вход второго сумматора по модулю , выходы двух остальных соединены с соответствующими входами блоков вычисления месторасположения первой и второй ошибок, на вторые входы которых подается сигнал с выхода сумматора по модулю , выходы блоков вычисления месторасположения первой и второй ошибок соединены с соответствующими входами блоков дешифрации, сигналы с выходов которых подаются на логический элемент ИЛИ, выход которого соединен со вторым входом блока инвертирования. Однако данное устройство требует больших аппаратурных затрат на построение блоков дешифрации и использует ПЗУ значительной емкости 3, стр. 131, рис. 5.3. В техническом решении поставлена задача разработки устройства норменной коррекции двойных ошибок с высоким быстродействием и невысокой аппаратурной сложностью. Техническим результатом, который может быть получен при использовании данной полезной модели, является декодер для норменной коррекции двойных ошибок с невысокой сложностью и высоким быстродействием. Устройство норменной коррекции двойных ошибок, содержащее блок вычисления синдрома, выход которого является входом блока вычисления нормы, выход которого является входом устройства, отличается тем, что в устройство введены регистр циклическо 2 60622010.04.30 го сдвига, генератор тактов, два триггера, счетчик сдвигов, селектор образующих норм циклотомических классов, логический элемент ИЛИ, два постоянных запоминающих устройства ПЗУ 1 - ПЗУ 2, блок вычисления сдвига, блок определения вектора ошибки, причем один из выходов блока вычисления нормы соединен со входом регистра циклического сдвига, а второй - со входом блока вычисления сдвига, выход генератора тактов соединен со входами двух триггеров, выход первого их которых соединен с блоком определения вектора ошибки, а второго - со счетчиком сдвигов, селектором норм образующих циклотомических классов и регистром циклического сдвига, выход которого соединен со входом селектора образующих норм циклотомических классов, выходы которого подаются на блоки ПЗУ 1, ПЗУ 2 и логический элемент ИЛИ, выход которого соединен с разрешающим входом первого триггера, с запрещающим входом второго триггера и со счетчиком сдвигов, выход которого подается на соответствующие входы блоков ПЗУ 1, ПЗУ 2, выход ПЗУ 1 соединен со входом блока вычисления сдвига, выход которого соединен со входом блока определения вектора ошибки, с другим входом которого соединен выход блока ПЗУ 2, один из выходов блока определения ошибки соединен с запрещающим входом первого триггера, а второй является выходом устройства. Сущность данной полезной модели заключается в том, что предлагаемое устройство позволяет корректировать двойные ошибки с высоким быстродействием и сократить объем ПЗУ, необходимый для хранения норм синдромов за счет использования норменных циклотомических классов. Вычисление вектора ошибки осуществляется следующим образом на основе нормы,вычисленной их синдрома принятого слова, с помощью селектора образующих норм циклотомических классов определяются адреса в блоках ПЗУ, из которых извлекается образующий вектор ошибок (еобр) и значение обр элемента обр - синдрома (еобр) - в поле Галуа. Далее, в зависимости от значений обр и тек - элемента тек - синдрома, вычисленного на основании принятого слова, вектор еобр видоизменяется, в результате чего определяется искомый вектор ошибок етек. Предложение иллюстрируется следующими чертежами. На фиг. 1 представлена структурная схема устройства, на фиг. 2 - структурная схема селектора образующих норм циклотомических классов, на фиг. 3 - структурная схема ПЗУ, на фиг. 4 - структурная схема блока вычисления сдвига, на фиг. 5 - структурная схема блока определения вектора ошибки. Реализация блока вычисления синдрома, блока вычисления нормы, триггеров, генератора тактов, регистра циклического сдвига, счетчика сдвигов известна. В этих блоках используются элементы И, ИЛИ, , сумматоры по модулю два. Устройство норменной коррекции двойных ошибок содержит блок 1 вычисления синдрома блок 2 вычисления нормы регистр циклического сдвига 3 генератор тактов 4 первый триггер 5, второй триггер 6 счетчик сдвигов 7 селектор норм циклотомических классов 8 логический элемент ИЛИ 9 два постоянных запоминающих устройства ПЗУ 1(10) - ПЗУ 2(11) блок 12 вычисления сдвига блок 13 определения вектора ошибки блок вычисления синдрома 1, выход 14 которого является входом блока вычисления нормы 2, первый выход 17 которого является одним из входов блока вычисления сдвига 12,второй выход 15 является входом регистра циклического сдвига 3, выход 16 которого подается на вход селектора образующих норм циклотомических классов 8, выходы 21, 22, 23 которого соединены с соответствующими входами блоков ПЗУ 1 10, ПЗУ 2 11 и логического элемента ИЛИ 9, выход 20 которого подается на вход счетчика сдвигов 7, разрешающий вход триггера 6 и запрещающий вход триггера 5, тактовым входом 18 которого является выход генератора тактов 4, а выход 19 блока 5 соединен с регистром циклического сдвига 3, селектором норм циклотомических классов 8 и счетчиком сдвигов 7, выход 24 которого соединен с соответствующим входом блоков ПЗУ 1 10 и ПЗУ 2 11, выход 25 блока 10 подается на один из входов блока вычисления сдвига 12, выход 27 которого является входом блока определения вектора ошибок 13, на второй вход которого подается сигнал с 3 60622010.04.30 выхода 26 блока 11, на третий вход - сигнал выхода 28 триггера 6, выход 29 блока 13 соединен с запрещающим входом блока 6, а выход 30 является выходом устройства (фиг. 1). Устройство работает следующим образом. Принятое кодовое слово поступает в блок вычисления синдрома 1, где вычисляется синдромпо принятым входным символам. Синдромпоступает на вход блока вычисления нормы 2, где вычисляется нормасиндромаи значение тек элемента текв поле Галуа. Значение нормы заносится в регистр циклического сдвига 3, а значение тек поступает на вход блока вычисления сдвига 12. Информация об образующих нормах норменных циклотомических хранится в селекторе образующих норм циклотомических классов 8, на вход 16 которого поступает значение из регистра циклического сдвига 3, а вход 19 является тактовым входом блока. При несрабатывании селектора по тактовому сигналу генератора тактов 4 значение регистра 3 циклически сдвигается и значение счетчика сдвигов увеличивается на единицу. При срабатывании селектора на одном из его выходов появляется единичный сигнал, который через выход 20 логического элемента ИЛИ 2 блокирует работу триггера 5 и разблокирует работу триггера 6. Информация об образующем векторе ошибок обр и о значении обр элемента обр(еобр) хранится в ПЗУ 1 и ПЗУ 2 соответственно. Сигналы с выходов блока 8 и блока 7 поступают на ПЗУ 1 10 и ПЗУ 2 11, на выходах которых формируются значения обр и еобр, поступающие соответственно на блок вычисления сдвига 12, на выходе которого формируются значения, служащие для преобразования еобр в искомый вектор ошибки етек,и на вход блока 13, на выходе которого формируется сигнал 30, представляющий собой искомый вектор ошибки. На фиг. 2 представлена структурная схема блока 8 селекции образующих норм циклотомических классов, содержащего блоки ПЗУ 31, 32, 33, на первый вход которых полается входной сигнал 16, на второй - входной сигнал 19, выходы 37, 38, 39 блоков 31, 32, 33 соединены соответственно с первыми входами логического элемента И, на вторые входы которых подается сигнал 16 и выходы 21, 22, 23 которых являются выходами блока. Блок работает следующим образом. По тактовому сигналу 19 значения, хранящиеся в ПЗУ 31, 32, 33, поступают на входы соответствующих элементов И 34, 35, 36, на другие входы которых подается значение с выхода регистра циклического сдвига 16. При срабатывании одного из логических элементов И на его выходе формируется единичный сигнал. На фиг. 3 представлена структурная схема ПЗУ 1 10, ПЗУ 2 11, содержащая блоки сравнения 40, 41, 42, на входы которых подается сигнал 24 и сигналы 21, 22, 23 соответственно, выходы 45, 46, 47 которых соответственно соединены со входами блоков ПЗУ 43, 44,45, выход 25 или 26 которых является выходом устройства. Блок работает следующим образом. По сигналу 24 счетчика сдвига, согласно одному из разрешающих сигналов 21, 22 и 23, на одном из выходов 46, 45 или 47 блока сравнения 40, 41 или 42 соответственно формируется сигнал, являющийся адресом, по которому в соответствующем блоке ПЗУ считывается вектор еобр, который поступает на выход 25,или б, поступающий на выход 26. На фиг. 4 изображена структурная схема блока 12 вычисления сдвига, содержащая сумматор по модулю 48, на входы которого подаются сигналы 17 и 25, а выход 27 является выходом блока. Блок работает следующим образом. На входы сумматора по модулюподаются значения тек элемента(етек) в поле Галуа с выхода 17 и обр элемента обр(обр) с выхода 25. На выходе этого блока формируется значение, равное (тек - 6) . На фиг. 5 представлена структурная схема блока 13 определения вектора ошибки, содержащего счетчик 49, на первый вход которого подается сигнал 27, второй вход которого соединен с тактовым выходом 28, сигнал которого также подается на вход регистра циклического сдвига 51, выход 52 элемента 49 соединен с первым входом логического элемента И 50, на второй вход которого подается 0, а выход 29 которого является выходом 4 60622010.04.30 блока, на второй вход регистра циклического сдвига 51 подается входной сигнал 25, а выходной сигнал блока 51 является выходным сигналом устройства. Блок работает следующим образом. Значение сигнала 27 заносится в счетчик 49, а сигнала 25 - в регистр циклического сдвига 51. По тактовому сигналу 28 счетчик уменьшает свое значение на единицу и сравнивает с нулем, подавая его по шине 52 на логический элемент И 50, регистр циклического сдвига осуществляет циклический сдвиг вектора еобр. При достижении счетчиком нулевого значения на выходе логического элемента И 50 формируется единичный сигнал 29, по которому подача тактовых сигналов 28 прекращается, в этом случает значение, считываемое из регистра 51, и является искомым вектором ошибок. Например, блок 1 вычисления синдрома кода 5 х 321,31 вычислил синдром(1111101100) блок вычисления нормы посчитал норму 14 и значение тек 16. Образующие норм циклоклассов равны 3, 7 и 15 (фиг. 6). Полученная норма циклически сдвигается трижды, до совпадения с образующей норменного циклотомического класса, равной 7. По сработавшему устройству селекции определяем, из какого ПЗУ необходимо извлекать данные, по значению счетчика сдвигов определяем адрес извлечения данных, полученная из ПЗУ информация равна еобр(0000000000000001000001000000000), б 0. Блок вычисления сдвига определил значение, на которое надо сдвинуть еобр(тек обр)(16 - 0) 3116. Блок определения текущего вектора ошибки циклически,сдвинув вектор еобр 16 раз, определил значение етек(10000010000000000000000000000000). Технико-экономическое преимущество предложенного устройства норменной коррекции двойных ошибок по сравнению с известными устройствами на основе переборного метода заключается в повышении быстродействия за счет уменьшения задержек при определении вектора ошибки. Это объясняется тем, что известные устройства нахождения вектора ошибки должны осуществить процедуру поиска синдрома в множестве синдромов большой мощности, что и приводит к задержкам. Например, при длине кода, корректирующего двойные ошибки,31 мощность множества синдромов при синдромном декодировании равна 465, мощность множества синдромов при норменном декодировании равна 31, модность норменного циклокласса равна 5, что позволяет получить выигрыш в 93 и 6 раз соответственно. Таким образом, предложенное устройство обладает более высоким быстродействием по сравнению с декодированием, основанным на переборных методах. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 6