устройство декодирования циклического кода хемминга

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

1. Устройство декодирования циклического кода Хемминга, содержащее последовательно соединенные регистр сдвига и первый блок исправления ошибок, а также делитель, первый выход которого соединен с первым входом дешифратора ошибок, выход которого соединен с вторым входом первого блока исправления ошибок, причем входы регистра сдвига и делителя соединены и являются входом устройства, отличающееся тем, что введены последовательно соединенные блок определения адреса исправляемого символа и второй блок исправления ошибок, выход которого является выходом устройства, кроме того, выход первого блока исправления ошибок соединен с вторым входом второго блока исправления ошибок, m выходов делителя соединены соответственно с m входами блока определения адреса исправляемого символа, сигнальный вход которого соединен с входом делителя, (m-1) выходов которого соединены соответственно с (m-1) входами дешифратора ошибок, при этом входы R регистра сдвига, делителя и блока определения адреса исправляемого символа соединены и являются входом начальной установки, входы C регистра сдвига, делителя и блока определения адреса исправляемого символа объединены и являются управляющим входом устройства, при этом блок определения адреса исправляемого символа содержит блок сравнения, выход которого соединен с первым входом элемента 2И и вторым входом элемента 2НЕ-И, а также D-триггер, выход которого соединен со вторым входом элемента 2И и первым входом элемента 2НЕ-И, выходы элементов 2И и 2НЕ-И соединены с соответствующими входами элемента 2ИЛИ, выход которого соединен с первым входом элемента 2И-НЕ, выход которого соединен с входом S RS-триггера, выход которого является выходом блока определения адреса исправляемого символа, кроме того, селективный счетчик импульсов, выход 2n которого соединен через инвертор с первым входом элемента 2НЕ-ИЛИ-НЕ, выход которого соединен с R входом RS-триггера, и R входами D-триггера и селективного счетчика импульсов, i-й выход которого соединен с C входом D-триггера, а (n+1)-й выход селективного счетчика соединен со вторым входом элемента 2И-НЕ, причем m входов блока сравнения являются соответствующими входами блока определения адреса исправляемого символа, второй вход элемента 2НЕ-ИЛИ-НЕ является входом начальной установки, вход C селективного счетчика импульсов является управляющим входом, а вход D D-триггера является сигнальным входом блока определения адреса исправляемого символа.

2. Устройство по п.1, отличающееся тем, что дешифратор ошибок содержит m элементов 2НЕ-И и элемент И, выход которого является выходом дешифратора, первые входы m элементов 2НЕ-И являются m входами дешифратора ошибок, вторые входы m элементов 2НЕ-И объединены и соединены с общей шиной, а выходы m элементов 2НЕ-И соединены с соответствующими входами элемента И.

3. Устройство по п.1, отличающееся тем, что селективный счетчик импульсов содержит счетчик импульсов, выходы которого соединены с соответствующими входами дешифратора, выходы которого являются i-м контрольным разрядом циклического кода Хемминга, (n+1)-м и 2n-м выходами селективного счетчика импульсов соответственно, а входы С и R счетчика импульсов являются управляющим и входом начальной установки соответственно.

Описание изобретения к патенту

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

Известное устройство декодирования циклического кода Хемминга приведено в книге Мак-Вильямс Ф.Д., Слоэн Н.Д.А. Теория кодов, исправляющих ошибки. М.: Связь, с.271, рис.9.5. Устройство содержит блок задержки, два формирователя для вычисления синдрома порождающего многочлена, блок исправления ошибок (сумматор по модулю 2), реализующий процедуру исправления ошибок Ченя, блок определения многочлена локаторов ошибок и формирователи для вычисления синдромов.

Недостатком данного устройства декодирования циклического кода Хемминга является сложность реализуемых алгоритмов, а также то, что для повышения исправляющей способности циклического кода размерности n=2^m-1 при кодировании необходимо уменьшать количество информационных символов в кодовом многочлене за счет увеличения числа проверочных символов.

Наиболее близким к предлагаемому является устройство декодирования циклического кода Хемминга, описанное в книге Шварцман В.О., Емельянов Г.А. Теория передачи дискретной информации. М.: Связь, 1979, с.309, рис.10.4, принятое за прототип.

Схема устройства-прототипа представлена на фиг.1, где обозначено:

1 - регистр сдвига;

2 - делитель;

3 - устройство исправления ошибки;

4 - дешифратор ошибки;

5, 6 - ключи.

Устройство-прототип содержит последовательно соединенные регистр сдвига 1 и устройство исправления ошибки 3, выход которого является выходом устройства, а также делитель 2, содержащий в цепи обратной связи ключ 5, выход делителя 2 через ключ 6 соединен с входом дешифратора ошибки 4, выход которого соединен с вторым входом устройства исправления ошибки 3. При этом входы регистра сдвига 1 и делителя 2 объединены и являются входом устройства.

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

Работа устройства начинается со сброса регистра сдвига 1 и делителя 2 в исходное состояние. Затем на вход устройства декодирования поступает кодовая комбинация длины n, при этом в течение длины кодовой комбинации ключ 5 замкнут, а ключ 6 разомкнут. В результате в регистре сдвига записывается принятая кодовая комбинация длины n, а в делителе 2 оказывается записанным синдром. Размыкается ключ 5 и замыкается ключ 6, и информация, записанная в делителе 2, унитарным кодом поступает в дешифратор ошибки 4, где определяется разряд, в котором обнаружена ошибка. С помощью тактовых импульсов происходит передача кода, записанного в регистре сдвига 1 на первый вход устройства исправления ошибки 3, на второй вход которого поступает сигнал с выхода дешифратора ошибки 4. Устройство исправления ошибки 3 представляет собой сумматор по модулю 2. Когда на выходе дешифратора ошибки 4 сигнал равен "1", то на выходе устройства исправления ошибки 3 происходит инверсия кода, поступающего на первый вход этого устройства 3. Когда на выходе дешифратора ошибки 4 сигнал равен "0", то на выходе устройства исправления ошибки 3 происходит повторение кода, поступающего на первый вход этого устройства 3. На выходе дешифратора ошибки 4 появляется уровень "1", когда разряд кода с выхода регистра сдвига 1 соответствует месту обнаруженной ошибки. В результате осуществляется исправление одного ошибочного символа на выходе устройства декодирования.

Недостатком устройства-прототипа является невозможность исправления более одного ошибочного символа входной информации, представляемой циклическим (n, k) кодом Хемминга.

Целью предлагаемого решения является повышение помехозащищенности передаваемой информации за счет увеличение числа исправляемых символов в циклическом (n, k) коде Хемминга, имеющем кодовое расстояние 3.

Для устранения указанных недостатков в устройство, содержащее последовательно соединенные регистр сдвига 1 и первый блок исправления ошибок 3, а также делитель, первый выход которого соединен с первым входом дешифратора ошибок 4, выход которого соединен с вторым входом блока исправления ошибок 3, причем входы регистра сдвига 1 и делителя 2 соединены и являются входом устройства, согласно изобретению введены последовательно соединенные блок определения адреса исправляемого символа 5, второй блок исправления ошибок 6, выход которого является выходом устройства, кроме того, выход первого блока исправления ошибок 3 соединен с вторым входом второго блока исправления ошибок 6, m выходов делителя 2 соединены соответственно с m входами блока определения адреса исправляемого символа 5, сигнальный вход которого соединен с входом делителя 2, (m-1) выходов которого соединены соответственно с (m-1) входами дешифратора ошибок 4, при этом входы "R" регистра сдвига 1, делителя 2 и блока определения адреса исправляемого символа 5 соединены и являются входом начальной установки, входы "С" регистра сдвига 1, делителя 2 и блока определения адреса исправляемого символа 5 объединены и являются управляющим входом устройства, при этом блок определения адреса исправляемого символа 5 содержит блок сравнения 5.2, выход которого соединен с первым входом элемента 2И 5.5 и вторым входом элемента 2НЕ-И 5.6, а также D-триггер 5.3, выход которого соединен с вторым входом элемента 2И 5.5 и первым входом элемента 2НЕ-И 5.6, выходы обоих элементов 2И 5.5 и 2НЕ-И 5.6 соединены с соответствующими входами элемента 2ИЛИ 5.8, выход которого соединен с первым входом элемента 2И-НЕ 5.1, выход которого соединен с первым входом RS-триггера 5.7, выход которого является выходом блока определения адреса исправляемого символа 5, кроме того, селективный счетчик импульсов 5.4, выход 2n которого соединен через инвертор 5.9 с первым входом элемента 2НЕ-ИЛИ-НЕ 5.10, выход которого соединен с вторым входом RS-триггера 5.7, и "R" входами D-триггера 5.3 и селективного счетчика импульсов 5.4, i-й выход которого соединен с "С" входом D-триггера 5.3, а (n+1)-й выход селективного счетчика 5.4 соединен с вторым входом элемента 2И-НЕ 5.1, причем m входов блока сравнения 5.2 являются соответствующими входами блока определения адреса исправляемого символа 5, второй вход элемента 2НЕ-ИЛИ-НЕ 5.10 является входом начальной установки, вход "С" селективного счетчика импульсов 5.4 является управляющим входом, а вход "D" D-триггера 5.3 является сигнальным входом блока определения адреса исправляемого символа 5.

Структурная схема предлагаемого устройства представлена на фиг.2, где обозначено:

1 - регистр сдвига;

2 - делитель;

3, 6 - первый и второй блок исправления ошибок;

4 - дешифратор ошибок;

5 - блок определения адреса исправляемого символа.

Предлагаемое устройство декодирования циклического кода Хемминга содержит последовательно соединенные регистр сдвига 1, первый 3 и второй 6 блоки исправления ошибок, а также делитель 2, m выходов которого соединены с соответствующими m входами дешифратора ошибок 4 и блока определения адреса исправляемого символа 5. При этом выход дешифратора ошибок 4 соединен с вторым входом первого блока исправления ошибок 3, а выход блока определения адреса исправляемого символа 5 - с вторым входом второго блока исправления ошибок 6, выход которого является выходом устройства. Кроме того, информационные входы регистра сдвига 1, делителя 2 и блока определения адреса исправляемого символа 5 соединены между собой и являются входом устройства. "R" входы регистра сдвига 1, делителя 2 и блока определения адреса исправляемого символа 5 соединены и являются входом начальной установки устройства. Входы "С" регистра сдвига 1, делителя 2 и блока определения адреса исправляемого символа 5 соединены и являются управляющими входами устройства.

Регистр сдвига 1 представляет собой последовательное соединение n D-триггеров с объединенными управляющими входами "С" и входами начальной установки "R", причем выход каждого D-триггера подсоединен к D-входу последующего. D-вход первого D-триггера регистра сдвига 1 является входом устройства, а выход последнего D-триггера является выходом регистра сдвига 1.

Оба блока исправления ошибок 3 и 6 выполнены на двухвходовых сумматорах по модулю 2.

На фиг.3 приведена блок-схема дешифратора ошибок 4; на фиг.4 - схема блока определения адреса исправляемого символа 5; на фиг.5 - схема блока сравнения 5.2 блока определения адреса исправляемого символа 5; на фиг.6 изображена схема селективного счетчика импульсов 5.4 блока определения адреса исправляемого символа 5.

Дешифратор ошибок 4 (фиг.3) содержит m элементов 2НЕ-И 4.1...4. m и элемент И 4.0, выход которого является выходом блока 4. Первые входы элементов 2НЕ-И 4.1...4. m являются m входами дешифратора ошибок 4 и соединены с соответствующими m выходами делителя 2, вторые входы элементов 2НЕ-И 4.1...4. m объединены и соединены с общей шиной. Выходы элементов 2НЕ-И 4.1...4. m соединены с соответствующими входами элемента И 4.0.

На фиг.4 приведена схема блока определения адреса исправляемого символа 5, где обозначено:

5.1 - элемент 2И-НЕ; 5.2 - блок сравнения; 5.3 - D-триггер; 5.4 - селективный счетчик импульсов; 5.5 - элемент 2И; 5.6 - элемент 2НЕ-И; 5.7 - RS-триггер; 5.8 - элемент 2ИЛИ; 5.9 - инвертор; 5.10 - элемент 2НЕ-ИЛИ-НЕ.

Блок определения адреса исправляемого символа 5 содержит блок сравнения 5.2, выход которого соединен с первым входом элемента 2И 5.5 и вторым (инверсным) входом элемента 2НЕ-И 5.6, а также D-триггер 5.3, выход которого соединен с вторым входом элемента 2И 5.5 и первым (инверсным) входом элемента 2НЕ-И 5.6, выходы элементов 2И 5.5 и 2НЕ-И 5.6 соединены с соответствующими входами элемента 2ИЛИ 5.8, выход которого соединен с первым входом элемента 2И-НЕ 5.1, выход которого соединен с первым входом RS-триггера 5.7, выход которого является выходом блока определения адреса исправляемого символа 5. Кроме того, селективный счетчик импульсов 5.4, выход 2n которого соединен через инвертор 5.9 с первым входом элемента 2НЕ-ИЛИ-НЕ 5.10, выход которого соединен с вторым входом RS-триггера 5.7, и "R" входами D-триггера 5.3 и селективного счетчика импульсов 5.4, i-й выход которого соединен с "С" входом D-триггера 5.3, а (n+1)-й выход селективного счетчика 5.4 соединен с вторым входом элемента 2И-НЕ 5.1. Причем m входов блока сравнения 5.2 являются входами блока 5. Второй вход элемента 2НЕ-ИЛИ-НЕ 5.10 является входом начальной установки. Вход "С" селективного счетчика импульсов 5.4 является управляющим входом. Вход "D" D-триггера 5.3 является сигнальным входом блока определения адреса исправляемого символа 5.

Блок сравнения 5.2 (фиг.5) содержит инвертор 8, выход которого соединен с вторыми входами u элементов 2И 7.1...7.u, выходы которых соединены с соответствующими входами элемента И 10, выход которого является выходом блока сравнения 5.2. Кроме того, v элементов 2НЕ-И 9.1...9.v, выходы которых соединены с соответствующими входами элемента И 10. Вторые входы элементов 2НЕ-И 9.1...9.v соединены с входом инвертора 8 и общей шиной. При этом первые входы элементов 2И 7.1...7.u и элементов 2НЕ-И 9.1...9.v являются m входами блока сравнения 5.2.

Селективный счетчик импульсов 5.4 (фиг.6) содержит счетчик импульсов 5.4.1, выходы которого соединены с соответствующими входами дешифратора 5.4.2. Входы "С" и "R" счетчика импульсов 5.4.1 являются управляющим и входом начальной установки соответственно. Выходы дешифратора 5.4.2 являются i-м контрольным разрядом циклического кода Хемминга, (n+1)-м и 2n-м выходами селективного счетчика импульсов 5.4 соответственно.

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

Установление декодирующего устройства циклического кода Хемминга в исходное состояние осуществляется после подачи импульса на входы начальной установки "R" регистра сдвига 1 и блока определения адреса исправляемого символа 5 (фиг.2). При этом обнуляются информационные выходы регистра сдвига 1 и селективный счетчик импульсов 5.4, RS-триггер 5.7 и D-триггер 5.3 блока определения адреса исправляемого символа 5 (фиг.4).

На первом этапе синхроимпульсы, поступающие на управляющий вход устройства декодирования (фиг.2), обеспечивают прием поступающей на вход последовательности импульсов регистром сдвига 1 и делителем 2. Последний используется для деления многочлена А(х) на порождающий многочлен g(x). В результате в делителе 2 получается остаток от деления где - примитивный элемент матрицы Н (2). На этом же этапе n-м синхроимпульсом в принимаемой кодовой последовательности выделяется контрольный разряд, содержимое которого регистрируется D-триггером 5.3 блока определения адреса исправляемого символа 5 (фиг.4).

На втором этапе осуществляется вывод информационной части кодового многочлена из регистра сдвига 1 на выход устройства декодирования циклического кода Хемминга (фиг.2) с одновременным поиском дешифратором ошибок 4 адресов возможных ошибочных символов, которые согласно выражению (4) исправляются в блоке исправления ошибок 3 в соответствии с известным алгоритмом Ченя. При этом осуществляется коррекция выходной информации во втором блоке исправления ошибок 6 путем прибавления к полученному коду многочлена I(х), если это необходимо по результатам анализа, осуществленного блоком определения адреса исправляемого символа 5.

Если многочлен R(x)=0, то делитель 2 после окончания первого этапа содержит адрес (локатор) ошибочного символа. Исправление его осуществляется в соответствии с известным алгоритмом Хемминга в блоке исправления ошибок 3 путем последовательного сдвига содержимого регистра сдвига 1 при выводе информации на выход устройства декодирования циклического кода Хемминга (фиг.2).

Анализ содержимого делителя 2 после каждого сдвига осуществляется дешифратором ошибок 4. Одновременно блок сравнения 5.2 блока определения адреса исправляемого символа 5 анализирует содержимое делителя 2 для выявления в нем контрольного символа, расположенного по адресу ⁱ.

Работа блока исправления ошибок 6 разрешается высоким уровнем RS-триггера 5.7 блока определения адреса исправляемого символа 5. При этом RS-триггер 5.7 устанавливается в единичное состояние низким уровнем на выходе элемента 2И-НЕ 5.1, который появляется по (n+1) управляющему синхроимпульсу, приходящему на втором этапе на управляющий вход устройства декодирования циклического кода Хемминга (фиг.2) при наличии высокого уровня на выходе элемента 2ИЛИ 14. На выходе элемента 2И 12, к которому подключен первый элемента 2ИЛИ 5.8, появится высокий уровень, при наличии высокого уровня на выходе D-триггера 5.3 (контрольный символ кодового многочлена не равен нулю) при условии, что на выходе блока сравнения 5.2 находится высокий уровень (многочлен На выходе элемента 2НЕ-И 5.7, к которому подключен второй вход элемента 2ИЛИ 5.8, появится высокий потенциал при наличии низкого уровня на выходе D-триггера 5.3 (контрольный символ кодового многочлена равен нулю) и низкого уровня на выходе блока сравнения 5.2 Соответственно высокий уровень на выходе элемента И 10 блока сравнения 5.2 появится только при наличии высоких уровней на выходе элементов 2И 7 и 2И-НЕ 9

Таким образом, в зависимости от вида многочлена на выходе устройства декодирования циклического кода Хемминга (фиг.2) в соответствии с формулами (4)-(6) возможны следующие варианты:

1. Тогда на выходе дешифратора ошибок 4 по i-му синхроимпульсу появится высокий уровень (по (i+1)-му синхроимпульсу сбросится), а на выходе блока определения адреса исправляемого символа 5 появится низкий, т.е. в блоке исправления ошибок 3 на i-м шаге произойдет замена 1-го символа на противоположный.

2. Тогда на выходе дешифратора ошибок 4 будет присутствовать низкий уровень, а на выходе блока определения адреса исправляемого символа 5 будет низкий, т.е. в блоке исправления ошибок 3 будет осуществлено инвертирование всех символов, поступивших из регистра сдвига 1.

3. Тогда на выходе дешифратора ошибок 4 по i-му синхроимпульсу появится высокий уровень (по (i+1)-му синхроимпульсу сбросится), а на выходе блока определения адреса исправляемого символа 5 появится высокий уровень, т.е. в блоке исправления ошибок 3 на 1-м шаге произойдет замена i-го символа на противоположный, а также инвертирование всех символов, поступивших из регистра сдвига 1.

Пример реализации способа декодирования циклического кода Хэмминга для n=2⁴-1=15. Выберем неприводимый многочлен g(x)=1+x+x⁴, для которого проверочная матрица Н имеет вид

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

Алгоритм следующий:

1. Вычисляется многочлен

2. По формуле (3) вычисляем многочлен

3. Формируется кодовый многочлен согласно выражению (1)

Примечание: контрольный символ

4. Задается вид многочлена ошибок согласно формулам (4)-(6)

Вариант а.

4. а. Многочлен найдем по формуле (7)

5, а. Определяется остаток от деления многочлена на порождающий многочлен g(x) на первом этапе

6, а. Исправляется ошибочный символ на обратный при R(x)=1 в делителе 2 после соответствующего количества сдвигов содержимого сдвигового регистра 1 и делителя 2 (так как R(x)=0 согласно п.5, а).

Вариант б.

4, б. Многочлен найдем по формуле (7)

5, б. Определяется остаток от деления многочлена на порождающий многочлен g(x) на первом этапе

R(x)=0.

6, б. Исправляются все символы многочлена на обратные, так как контрольный символ равен нулю согласно п.5, б.

Вариант в.

4, в. Многочлен найдем по формуле (7)

5, в. Определяется остаток от деления многочлена на порождающий многочлен g(x) на первом этапе

6, в. Исправляются все символы многочлена на обратные, так как контрольный символ равен нулю и многочлен R(x)=0 согласно п.5, в. Исправляется ошибочный символ на обратный при R(x)=1 в делителе 2 после соответствующего количества сдвигов содержимого сдвигового регистра 1 и делителя 2.

Предложенное устройство может исправлять помимо одиночных ошибок, также и n или (n-1) ошибочных символов в циклическом (n, k) коде Хемминга (размерности n) за счет включения в устройство блока определения адреса исправляемого символа 5 и второго блока исправления ошибок 6.

Сущность алгоритма, реализуемого устройством декодирования циклического кода Хемминга, сводится к следующему.

Из многочлена, описывающего циклический код Хемминга, содержащего m членов

формируется кодовый многочлен

где - проверочные символы, являющиеся остатком от деления многочлена на неприводимый многочлен g(x)=1+x+...+x^m, являющимся порождающим для данного циклического кода Хемминга.

Многочлен (х) можно также получить с помощью проверочной прямоугольной матрицы размером n×m:

где - примитивный элемент, степени которого порождают конечное поле Галуа GF(2^m) по модулю g(x). В этом случае

где k - степени ненулевых членов многочлена .

Так как в канале передачи присутствуют помехи, то получим многочлен ошибок , который примет одну из следующих форм:

где I(х) - единичный многочлен, содержащий n ненулевых членов.

Тогда на приемном конце кодовый многочлен А(х) примет следующий вид:

Нахождение и исправление ошибочных символов в кодовом многочлене в декодирующем устройстве циклического кода Хэмминга осуществляется следующим образом.

Устройство декодирования приводится в исходное состояние, когда регистр сдвига 1 и блок определения адреса исправляемого символа 5 обнуляются. Затем происходит работа в два этапа.

На первом этапе синхроимпульсы, поступающие на вход устройства декодирования циклического кода Хемминга, последовательно записываются в регистре сдвига 1. В результате чего осуществляется прием кодового многочлена Одновременно эти импульсы поступают на вход делителя 2, где осуществляется деление кодового многочлена (7) на порождающий многочлен g(x). В результате в делителе 2 получается остаток где - примитивный элемент матрицы Н (2).

На этом этапе n-ым синхроимпульсом в принимаемой кодовой последовательности выделяется контрольный разряд и запоминается.

На втором этапе осуществляется вывод информационной части кодового многочлена из регистра сдвига 1 на вход устройства декодирования с одновременным поиском дешифратором ошибок 4 адресов возможных ошибочных символов, которые согласно выражению (4) исправляются в соответствии с известным алгоритмом Ченя. При этом осуществляется коррекция выходной информации во втором блоке исправления ошибок 6 путем прибавления к полученному коду многочлена I(х), если это необходимо по результатам анализа, осуществленного блоком определения адреса исправляемого символа 5.

Если многочлен R(x)=0, то делитель 2 содержит адрес (локатор) ошибочного символа. Исправление его осуществляется в соответствии с известным алгоритмом Хемминга путем последовательного сдвига содержимого регистра сдвига 1.

Анализ содержимого делителя 2 производится после каждого сдвига. Одновременно осуществляется анализ содержимого делителя 2 для выявления в нем контрольного символа, расположенного по адресу ⁱ.

По сравнению с прототипом в предлагаемом устройстве появляется возможность исправления более одного ошибочного символа входной информации, представляемой циклическим (n, k) кодом Хемминга, имеющим кодовое расстояние 3, что обеспечивает повышение помехозащищенности передаваемой информации.