Способ декодирования циклических кодов с "жестким" решением по вектору-указателю и устройство его реализующее

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

 

Изобретение относится к области техники связи и, в частности, к системам передачи информации, в которых для ее защиты от искажений в канале связи применяются циклические БЧХ-коды и их модификации. Изобретение может быть использовано в кодеках (кодер-декодер) систем передачи и хранения дискретной информации.

Известен способ декодирования циклических БЧХ-кодов [1-3], который включает в себя вычисление расширенного синдрома, затем разложение его на суперпозицию строк расширенной проверочной матрицы, которое однозначно задает вектор ошибки из упорядоченного по весу смежного класса векторов ошибок. После чего осуществляют выбор в качестве вектора коррекции при «жестком» решении лидера смежного класса векторов ошибок. И в завершении процесса декодирования выполняется инверсия тех элементов в систематической части кодового слова, номера которых соответствуют позициям ненулевых элементов вектора коррекции.

При декодировании расширенных циклических кодов с «жестким» решением предлагаются варианты способов [1-3], в которых перед декодированием из полученного по каналу связи возможно искаженного кодового слова удаляют элемент расширения.

При декодировании усеченных циклических кодов с «жестким» решением предлагаются варианты способов [1-3], в которых перед декодированием в начало полученного по каналу связи возможно искаженного кодового слова добавляют нулевые элементы, количество которых равно величине укорочения. Очевидно, что добавленные в начало нулевые элементы не могут быть искажены в канале связи, так как они по нему не передавались. Недостатком способа [1-2] является то, что он обладает высокой вычислительной сложностью ν_сл, которая пропорциональна:

где w - вес (количество ненулевых элементов) проверочного многочлена циклического кода;

t - количество искаженных бит в кодовом слове.

Техническим результатом является повышение скорости декодирования циклических кодов.

Для достижения указанного технического результата предложен способ декодирования циклического кода, в котором поиск вектора коррекции в процессе формирования упорядоченного по весу смежного класса векторов ошибок осуществляется в соответствии со значениями элементов вектора-указателя. Вектор-указатель позволяет существенно сократить количество формируемых ветвей дерева упорядоченного по весу смежного класса векторов ошибок за счет исключения наиболее длинных (векторов ошибок большого веса).

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

Свойства вектора-указателя, которые следуют из свойств расширенной проверочной матрицы [2-3]:

1. Если кодовое слово исказила однократная или t-кратная ошибка, синдром которой сформирован непересекающимися в ненулевых позициях строками расширенной проверочной матрицы, тогда элементы вектора-указателя на искаженных позициях будут равны весу проверочного многочлена w;

2. Если кодовое слово искажено t-кратной ошибкой, синдром которой сформирован пересекающимися в ненулевых позициях строками расширенной проверочной матрицы, тогда несколько элементов вектора-указателя примут значения меньше, чем w, причем хотя бы один элемент вектора-указателя, указывающий на искаженную позицию, будет иметь максимальное значение.

Способ декодирования циклического кода с использованием упорядоченного по весу смежного класса векторов ошибок и вектора-указателя:

1. Вычислить расширенный синдром и вектор-указатель декодируемого, возможно искаженного в канале связи, кодового слова.

2. Если расширенный синдром равен нулевому вектору, перейти к п.11.

3. Если в векторе-указателе есть элементы, значения которых равны весу w, то сформировать вектор коррекции из нулевого вектора с единичными элементами в позициях, соответствующих элементам вектора-указателя веса w, и перейти к п.10.

4. Выбрать любой ненулевой элемент расширенного синдрома и сформировать w элементов для возможных начал фрагментов векторов ошибок смежного класса.

5. Выбрать в качестве наиболее вероятных только те элементы начал фрагментов векторов ошибок смежного класса, позиции которых соответствуют максимальным значениям элементов вектора-указателя.

6. Вычислить текущий расширенный синдром и вектор-указатель для каждого вновь сформированного фрагмента вектора ошибки смежного класса.

7. Если в одном из векторов-указателей имеются элементы со значениями w, то сформировать вектор коррекции из вектора ошибки, соответствующего данному вектору-указателю, в котором инвертировать элементы в позициях, в которых расположены элементы вектора-указателя, имеющие вес w, и перейти к п.10.

8. Выбрать любой ненулевой элемент в каждом текущем расширенном синдроме и сформировать w возможных продолжений фрагментов векторов ошибок смежного класса.

9. Выбрать только те элементы продолжения фрагментов векторов ошибок смежного класса, позиции которых соответствуют максимальным значениям элементов вектора-указателя и перейти к п.6.

10. Сложить по mod 2 принятое искаженное кодовое слово с сформированным вектором коррекции.

11. Выделить систематическую часть кодового слова.

Устройство, реализующее способ декодирования циклических кодов с «жестким» решением по вектору-указателю (фиг.1), содержит:

- блок вычисления синдрома и вектора-указателя - 1;

- блок формирования вектора коррекции - 2;

- блок формирования начальных элементов векторов ошибок - 3;

- блок вычисления текущего синдрома и текущего вектора-указателя - 4;

- блок завершения формирования вектора коррекции - 5;

- блок формирования элементов продолжения векторов ошибок - 6;

- блок коррекции - 7;

- блок выделения систематической части кодового слова - 8;

- оперативное запоминающее устройство - 9.

Блок вычисления синдрома и вектора-указателя 1 вычисляет расширенный синдром и вектор-указатель декодируемого кодового слова циклического кода.

Блок формирования вектора коррекции 2 формирует вектор коррекции, когда в векторе-указателе присутствуют элементы, значения которых равны весу проверочного многочлена w кода.

Блок формирования начальных элементов векторов ошибок 3 определяет исходные ненулевые позиции векторов ошибок формирующегося смежного класса. Расширенная проверочная матрица определяет w начальных ненулевых бит векторов ошибок смежного класса по любому ненулевому элементу расширенного синдрома.

В блоке формирования начальных элементов векторов ошибок - 3 из w начальных ненулевых бит векторов ошибок выбираются только те, которые соответствуют позициям вектора-указателя, в которых расположены максимальные значения. Выбранные ненулевые начальные значения заносятся в формируемые и хранящиеся в оперативном запоминающемся устройстве 9 векторы ошибок смежного класса вместе со своими расширенными синдромами и векторами-указателями. Блок вычисления текущего синдрома и текущего вектора-указателя 4 последовательно перебирает вновь сформированные фрагменты векторов ошибок, сохраненные в оперативном запоминающемся устройстве 9, вычисляет для каждого из них новый текущий синдром, который является суммой по mod 2 предшествующего синдрома и строки расширенной проверочной матрицы, номер которой соответствует позиции вектора-указателя, выбранной в блоке формирования начальных элементов векторов ошибок 3. Затем для каждого текущего расширенного синдрома вычисляется вектор-указатель. Вычисленный текущий синдром и вычисленный вектор-указатель запоминается в оперативном запоминающем устройстве 9 совместно со своим фрагментом вектора ошибки. Если один из элементов текущего вектора-указателя принимает максимальное значение, равное w, то вектор-указатель и соответствующий фрагмент вектора ошибки передается в блок завершения формирования вектора коррекции 5. Работа блока вычисления текущего синдрома и текущего вектора-указателя 4 завершается. Блок завершения формирования вектора коррекции 5 дополняет вектор коррекции элементами, позиции которых соответствуют элементам текущего вектора-указателя, со значениями равные w. Для этого в векторе ошибки инвертируются элементы в позициях, в которых элементы вектора-указателя имеют значение w.

Блок формирования элементов продолжения векторов ошибок 6 последовательно перебирает все вновь сформированные синдромы и для каждого из них формирует новый набор возможных продолжений текущих фрагментов векторов ошибок. Для этого выбирается любой ненулевой элемент синдрома и в соответствии с расширенной проверочной матрицей определяется w возможных продолжений текущего фрагмента вектора ошибки. Вновь сформированные w возможных фрагментов сохраняются с текущим синдромом в оперативном запоминающем устройстве 9 и управление передается блоку вычисления текущего синдрома и текущего вектора-указателя 4.

Блок коррекции 7 выполняет исправление ошибок в искаженном кодовом слове по критерию максимального правдоподобия. Для этого искаженное кодовое слово, поступившее с входа блока вычисления синдрома и вектора-указателя 1, складывается по mod 2 с вектором коррекции, который сформирован либо в блоке формирования вектора коррекции 2, либо в блоке завершения формирования вектора коррекции 5. Вектор коррекции является лидером смежного класса векторов ошибок [2-3].

Блок выделения систематической части кодового слова 8 формирует информационную последовательность из кодового слова циклического кода. В нем выделяется систематическая часть откорректированного или неискаженного кодового слова и передается на выход для дальнейшей обработки.

Оперативное запоминающее устройство 9 выполняет сохранение текущих расширенных синдромов, соответствующих им векторов-указателей и фрагментов векторов ошибок смежного класса.

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

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

Если расширенный синдром является нулевым вектором, то кодовое слово по критерию максимального правдоподобия не искажено, и оно передается в блок выделения систематической части кодового слова 8.

Если в вычисленном векторе-указателе присутствуют элементы, имеющие значение w, то обнаружен вектор коррекции. Вектор-указатель передается в блок формирования вектора коррекции 2.

Если расширенный синдром не является нулевым вектором и в вычисленном векторе-указателе присутствуют элементы, значения которых меньше w, то расширенный синдром и вектор-указатель передаются в блок формирования начальных элементов векторов ошибок 3.

В блоке формирования начальных элементов векторов ошибок 3 по любому ненулевому элементу расширенного синдрома с помощью расширенной проверочной матрицы определяются позиции, с которых могут начинаться векторы ошибок смежного класса. Сформированные позиции прореживаются с учетом значений элементов вектора-указателя - выбираются только те, которые соответствуют максимальным значениям элементов вектора-указателя. Прореженные позиции позволяют сформировать ненулевые начальные элементы фрагментов векторов ошибок смежного класса, которые вместе с расширенным синдромом запоминаются в оперативном запоминающем устройстве 9.

Затем запускается блок вычисления текущего синдрома и текущего вектора-указателя 4. Блок вычисления текущего синдрома и текущего вектора-указателя 4 последовательно перебирает вновь сформированные фрагменты векторов ошибок и формирует для каждого из них новый текущий синдром. Текущий синдром является суммой по mod 2 предшествующего синдрома и строки расширенной проверочной матрицы, номер которой соответствует позиции вектора-указателя, выбранной в блоке формирования начальных элементов векторов ошибок 3. Затем для каждого текущего расширенного синдрома вычисляется вектор-указатель. Сформированный текущий синдром и вычисленный вектор-указатель запоминается в оперативном запоминающем устройстве 9 совместно со своим фрагментом вектора ошибки.

Если один или несколько элементов текущего вектора-указателя принимает значение, равное w, то вектор-указатель и соответствующий ему фрагмент вектора ошибки передаются в блок завершения формирования вектора коррекции 5, иначе запускается блок формирования элементов продолжения векторов ошибок 6.

Блок формирования элементов продолжения векторов ошибок 6 последовательно перебирает вновь вычисленные текущие расширенные синдромы, для каждого из которых он определяет возможные ненулевые элементы для продолжения фрагмента вектора ошибки. Из полученного набора возможных элементов выбирает только те, которые соответствуют максимальным значениям вектора-указателя. Они сформировывают новые фрагменты векторов ошибок, которые запоминаются в оперативном запоминающем устройстве 9. Когда просмотр всех вновь созданных в блоке вычисления текущего синдрома и текущего вектора-указателя 4 расширенных синдромов завершен, управление вновь передается блоку вычисления текущего синдрома и текущего вектора-указателя 4.

Блок завершения формирования вектора коррекции 5 запускается после передачи в него из блока вычисления текущего синдрома и текущего вектора-указателя 4 фрагмента вектора ошибки и его вектор-указатель, в котором хотя бы один из элементов имеет максимальное значение, равное w. Сформированный вектор коррекции передается в блок коррекции 7, в котором происходит исправление искаженных позиций кодового слова по критерию максимального правдоподобия.

В блоке коррекции 7 выполняется поразрядное сложение по mod 2 искаженного кодового слова с вектором коррекции. Откорректированное кодовое слово передается в блок выделения систематической части кодового слова 8, в котором выделяется систематическая часть и передается на выход для дальнейшей обработки.

Декодирование кодового слова циклического кода завершено.

Реализация устройства, реализующего способ, может быть аппаратной, программной или аппаратно-программной.

Способ декодирования с использованием вектора-указателя циклических кодов с «жестким» решением может быть применен и для расширенных кодов. Расширение циклического БЧХ-кода не приводит к возрастанию его исправляющей способности, поэтому перед декодированием в декодируемом кодовом слове необходимо удалить бит «четности» (бит расширения).

Способ декодирования с использованием вектора-указателя циклических кодов с «жестким» решением применяется и для усеченных (укороченных) кодов. В этом случае необходимо в начало декодируемого кодового слова добавить нулевые элементы, количество которых соответствует параметру усечения. При выборе возможных элементов для продолжений фрагмента векторов ошибок смежного класса по п.5 и п.9 рассматриваемого способа исключают из рассмотрения и те, которые попадают на позиции усеченных элементов кодового слова. Это снижает количество формируемых фрагментов векторов ошибок смежного класса, что приведет к повышению быстродействия декодирования.

Достигаемым техническим результатом предложенного модифицированного способа декодирования циклических кодов с «жестким» решением является многократное повышение быстродействия способа декодирования циклических кодов с использованием упорядоченного по весу смежного класса векторов ошибок [1], который относится к классу способов декодирования по критерию максимального правдоподобия.

Список литературы

1. Патент на изобретение «Способ синдромного декодирования циклического кода (варианты)» №2340088, зарегистрировано в Государственном реестре изобретений РФ 27.11.2008 г.

2. Хмельков А.Н. Оптимальные синдромные декодеры циклических линейных блочных кодов // Радиотехника. 2007. №12. С.74-82.

3. Хмельков А.Н. Расширенный синдром циклического линейного блочного кода. Радиотехника. 2007. №12. С.67-73.

1. Способ декодирования циклического кода, заключающийся в том, что для принятого возможно искаженного кодового слова вычисляют расширенный синдром, по любому ненулевому элементу которого, используя расширенную проверочную матрицу, определяют на первом шаге возможные начальные элементы фрагментов векторов ошибок смежного класса и вычисляют для каждого вновь образованного фрагмента вектора ошибок текущий расширенный синдром, на втором и каждом последующем шаге по любому ненулевому элементу каждого из текущих синдромов, используя расширенную проверочную матрицу, определяют возможные элементы для продолжения фрагментов векторов ошибок смежного класса и вычисляют для каждого из них текущий расширенный синдром, при этом лидер веса t смежного класса векторов ошибок формируют на t-том шаге, когда один из текущих синдромов преобразуют в нулевой вектор, затем корректируют искаженное кодовое слово с помощью вектора коррекции и выделяют систематическую часть откорректированного кодового слова, отличающийся тем, что каждому текущему синдрому устанавливается в однозначное соответствие текущий вектор-указатель, элементами которого является число обращений к соответствующим строкам расширенной проверочной матрицы при формировании расширенных синдромов, при этом, используя вектор-указатель, уменьшают количество элементов для вновь формируемых фрагментов векторов ошибок за счет выбора только тех, которые соответствуют его максимальным значениям.

2. Способ по п. 1, отличающийся тем, что при декодировании расширенного циклического кода с «жестким» решением предварительно удаляют бит четности (бит расширения).

3. Способ по п. 1, отличающийся тем, что при декодировании усеченных (укороченных) циклических кодов с «жестким» решением предварительно в начало каждого декодируемого кодового слова добавляют нулевые элементы, количество которых равно параметру усечения, и при выборе элементов для продолжения фрагмента векторов ошибок с помощью вектора-указателя выполняют выбор только тех, которые не попадают на нулевые усеченные элементы.

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