СПОСОБ ДЕКОДИРОВАНИЯ КОДОВ БОУЗА-ЧОУДХУРИ-ХОКВИНГЕМА ПО МАКСИМУМУ ДИСКРЕТНОЙ ФУНКЦИИ ПРАВДОПОДОБИЯ С ПРИМЕНЕНИЕМ ГРАФОВ БЫСТРЫХ ПРЕОБРАЗОВАНИЙ Российский патент 2012 года по МПК H03M13/00 

Область техники, к которой относится изобретение.

Данное изобретение относится к декодированию помехоустойчивых кодов Боуза-Чоудхури-Хоквингема (БЧХ).

Уровень техники.

Известны способы декодирования БЧХ кодов, использующие алгоритмы Питерсона-Горенстейна-Цирлера (ПГЦ), Берлекэмпа-Месси, Евклида и Форни [2]. Общим для этих алгоритмов является выбор элементов полей Галуа в качестве алфавита кода. При этом задача декодирования сводится к такой обработке сигнала, которая будет эквивалентна решению алгебраической системы нелинейных уравнений и нахождению корней, которые локализуют ошибки. Способы декодирования отличаются друг от друга подходом к решению алгебраической системы нелинейных уравнений.

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

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

Данный способ основывается на относительно простом математическом аппарате, но также требует большого количества операций (времени) на декодирование БЧХ кодов, как и способы декодирования на основе алгоритмов ПГЦ, Берлекэмпа-Месси, Евклида и Форни.

Раскрытие изобретения.

Целью изобретения является разработка нового способа декодирования, с применением обработки сигналов, основанной на быстрых преобразованиях Уолша-Адамара с дальнейшей оценкой по максимуму дискретной функции правдоподобия - быстрого метода правдоподобия.

Предлагаемое техническое решение позволит уменьшить количество операций (времени) на декодирование кода БЧХ по сравнению с декодированием по максимуму дискретной функции правдоподобия и декодированием с помощью алгоритмов ПГЦ, Берлекэмпа-Месси, Евклида и Форни.

Сущность нового способа декодирования заключается в следующем.

Принятую последовательность двоичных символов разбивают на кодовые слова. В каждом кодовом слове производят перестановку двоичных символов таким образом, чтобы получить слово, принадлежащее матрице Уолша-Адамара.

Кодовое слово, принадлежащее матрице Уолша-Адамара, перемножают с опорной транспонированной матрицей Уолша-Адамара. При вычислении произведения для сокращения количества операций реализуют обработку сигнала, основанную на быстрых преобразованиях Уолша-Адамара для данного кода. Это позволяет сократить количество операций (времени) на декодирование кода БЧХ, по сравнению с декодированием по максимуму дискретной функции правдоподобия, когда производят перемножение каждого принятого кодового слова на опорную транспонированную матрицу, состоящую из всего множества кодовых слов для данного кода.

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

Для определения порядка перестановки символов в кодовом слове и приведения опорной матрицы к матрице Уолша-Адамара, из всего множества кодовых слов составляют матрицу. Матрицу разбивают на циркулянты M₁(g(x)), … M_Z(g(x)), размерности n×n, где n - длина кодового вектора. Столбцы каждого циркулянта нумеруют в соответствии с комбинациями-блоками, с которых эти столбцы начинаются. Число символов l в комбинациях-блоках определяют исходя из соотношения 2^l=n+1. Производят перестановку столбцов, располагая их в порядке возрастания номеров столбцов, в результате получают циркулянты . Порядок перестановки столбцов в циркулянтах определяет порядок перестановки символов в кодовом слове. При перестановке символов сохраняют соответствие номеров символов в кодовом слове и номеров ячеек регистра слов кода БЧХ.

Строки каждого из циркулянтов M₁(g(x)), … M_Z(g(x)) нумеруют в соответствии с l двоичными старшими разрядами, полученные номера присваивают строкам циркулянтов . Производят перестановку строк, располагая их таким образом, чтобы после добавления к полученным циркулянтам слева столбца, сверху строки из одних нулей и перевода кодовых элементов в сигнальные, получить матрицы Уолша-Адамара.

Краткое описание чертежей.

Фиг.1 - структурно-функциональная схема реализации декодирования кода БЧХ (15, 5) с помощью заявленного способа декодирования.

Фиг.2 - структурно-функциональная схема реализации схемы перекрестных связей 3 для декодирования кода БЧХ (15, 5) с помощью заявленного способа декодирования.

Фиг.3 - структурно-функциональная схема реализации устройства перемножения кодового слова с опорной транспонированной матрицей 4, с использованием быстрых преобразований Уолша-Адамара для кода БЧХ (15, 5).

Осуществление изобретения.

Для достижения указанных и других преимуществ и в соответствии с назначением настоящего изобретения способ декодирования кодов Боуза-Чоудхури-Хоквингема по максимуму дискретной функции правдоподобия с применением графов быстрых преобразований содержит этап приведения опорной матрицы к матрице Уолша-Адамара, на котором определяют порядок перестановки символов в принятом кодовом слове. Для этого из всего множества кодовых слов составляют матрицу. Матрицу разбивают на циркулянты M₁(g(x)), … M_Z(g(x)), размерности n×n, где n - длина кодового вектора. Столбцы каждого циркулянта нумеруют в соответствии с комбинациями-блоками, с которых эти столбцы начинаются. Число символов l в комбинациях-блоках определяют исходя из соотношения 2^l=n+1. Производят перестановку столбцов, располагая их в порядке возрастания номеров столбцов, в результате получают циркулянты . Порядок перестановки столбцов в циркулянтах определяет порядок перестановки символов в кодовом слове. При перестановке символов сохраняют соответствие номеров символов в кодовом слове и номеров ячеек регистра слов кода БЧХ.

Строки каждого из циркулянтов M₁(g(x)), … M_Z(g(x)) нумеруют в соответствии с l двоичными старшими разрядами, полученные номера присваивают строкам циркулянтов . Производят перестановку строк, располагая их таким образом, чтобы после добавления к полученным циркулянтам слева столбца, сверху стоки из одних нулей и перевода кодовых элементов в сигнальные, получить матрицы Уолша-Адамара.

Заявленный способ декодирования содержит этап, на котором после разбиения принятой последовательности двоичных символов на кодовые слова, в каждом кодовом слове производят перестановку двоичных символов таким образом, чтобы получить слово, принадлежащее матрице Уолша-Адамара. Порядок перестановки двоичных символов в кодовом слове определен на предыдущем этапе.

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

Из полученного множества значений (спектра принятого слова) выделяют максимальное, которому соответствует переданное слово.

Возможность реализации заявленного изобретения рассмотрим на примере декодирования кода БЧХ (15, 5).

Согласно фиг.1 для реализации предлагаемого способа декодирования в приемном устройстве 1 производят обработку принятого сигнала, выделение последовательности двоичных символов и разбиение ее на кодовые слова. Кодовые слова кода БЧХ (15, 5) с выхода приемного устройства 1 попадают в регистры слов кода БЧХ 2. Для кода БЧХ (15, 5) таких регистров два. Соответственно две схемы перекрестных связей 3, два устройства, реализующих перемножение кодового слова с опорной транспонированной матрицей, с использованием быстрых преобразований Уолша-Адамара 4. Таким образом, после приемного устройства 1 имеется два канала, отличающихся только тем, что логика работы каждого из устройств 4 определяется своей опорной транспонированной матрицей. Так как каналы идентичны на фиг.1 первый канал показан детально, второй канал показан сокращенно. Далее будем рассматривать только один канал.

Из регистра слов кода БЧХ 2 каждое слово попадает в схему перекрестных связей 3. Логика работы схемы перекрестных связей для кода БЧХ (15, 5) представлена на фиг.2.

Для определения логики работы схемы перекрестных связей для кода БЧХ (15, 5) и порядка перестановки символов в кодовом слове необходимо привести опорную матрицу, состоящую из всего множества кодовых слов кода БЧХ (15, 5) к виду матрицы Уолша-Адамара.

Определим порождающий полином кода БЧХ (15, 5) [2], на основе произведений неприводимых полиномов g₁(x)=x⁴+x+1, g₂(x)=x⁴+x³+x²+x+1, g₃(x)=x²+x+1 в виде g(x)=g₁(x)·g₂(x)·g₃(x)=x¹⁰+x⁸+x⁵+x⁴+x²+x+1.

Так как deg g(x)=10, то число проверочных символов r=10. Число информационных символов k=n-r=15-10=5, следовательно, число кодовых слов 2⁵=32. Определим множество всех кодовых слов кода БЧХ (15, 5), приведенное в столбце 4 табл.1, как произведение кодируемого вектора m_i(х), указанного в столбце 2 и порождающего полинома g(x), найденного ранее.

При анализе множества кодовых слов из столбца 4 табл.1 можно заметить, что каждому кодовому слову, содержащему комбинацию из четырех идущих подряд единиц, соответствует противоположное слово по двоичным символам, содержащее комбинацию из четырех идущих подряд нулей, например:

V₃=100110101111000 и V₂₆=011001010000111.

Приведем пары номеров кодовых слов, противоположных по двоичным символам: 5-28, 6-31, 9-16, 10-19, 12-21, 15-22, 17-8, 18-11, 20-13, 23-14, 24-1, 27-2, 29-4, 30-7.

В соответствии с противоположностью кодовых слов можно утверждать, что в табл.1 содержатся два циркулянта, противоположных по двоичным символам. Запишем первый циркулянт M₁(g(x)) и пронумеруем его столбцы в соответствии с 4-разрядными комбинациями-блоками, с которых эти столбцы начинаются:

Пронумеруем строки циркулянта M₁(g(x)) в соответствии с четырьмя двоичными старшими разрядами с 11-го по 14-ый. Присвоим полученные номера строкам циркулянта Расположим строки циркулянта в следующей последовательности: 5, 11, 14, 6, 3, 13, 8, 12, 9, 7, 2, 10, 15, 1, 4.

Полученная матрица является матрицей Уолша-Адамара. Следовательно, и противоположный по двоичным символам циркулянт, содержащийся в табл.1, можно привести к матрице Уолша-Адамара аналогичным способом.

Порядок перестановки столбцов матрицы, состоящей из множества кодовых слов кода БЧХ (15, 5), для ее приведения к виду матрицы Уолша-Адамара, определяет логику работы схемы перекрестных связей. Таким образом, схема перекрестных связей позволяет сохранить связь ячеек регистра слов кода БЧХ со столбцами матрицы, используемой в качестве весовой при декодировании по максимуму дискретной функции правдоподобия.

После схемы перекрестных связей 3 полученное слово, принадлежащее к матрице Уолша-Адамара, перемножают с опорной транспонированной матрицей Уолша-Адамара, с помощью устройства 4. Логика работы устройства 4 представлена на фиг.3 и соответствует графу быстрых преобразований Уолша-Адамара. Использование быстрых преобразований Уолша-Адамара для получения результата перемножения позволяет снизить количество операций (уменьшить время) на декодирование кода БЧХ (15, 5), по сравнению с декодированием по максимуму дискретной функции правдоподобия, что соответствует заявленному техническому результату.

Из полученного множества значений (спектра принятого слова) выделяют максимальное с помощью схемы отбора максимума 5. Максимальному значению соответствует переданное слово.

Литература

1. Берлекэмп Э. Алгебраическая теория кодирования. - М.: Мир, 1971, с.186.

2. Блейхут Р. Теория и практика кодов, контролирующих ошибки. - М.: Мир, 1986, сс.193-228.

3. Мак-Вильямс Ф.Дж., Н.Дж.А.Слоуэн. Теория кодов, исправляющих ошибки. - М.: Связь, 1979, сс.287-288.

Изобретение относится к декодированию помехоустойчивых кодов Боуза-Чоудхури-Хоквингема (БЧХ). При реализации способа декодирования принятую последовательность двоичных символов разбивают на кодовые слова. В каждом кодовом слове производят перестановку двоичных символов таким образом, чтобы получить слово, принадлежащее матрице Уолша-Адамара. Для определения порядка перестановки символов в кодовом слове из всего множества кодовых слов составляют матрицу и приводят ее к матрице Уолша-Адамара путем переупорядочивания столбцов и строк. Кодовое слово, принадлежащее матрице Уолша-Адамара, перемножают с опорной транспонированной матрицей Уолша-Адамара. При этом реализуют обработку сигнала эквивалентную быстрому преобразованию Уолша-Адамара для данного кода. Результатом перемножения является множество значений, из которого выделяют максимальное, максимальному значению соответствует переданное слово. Техническим результатом является сокращение количества операций (времени) на декодирование кода БЧХ по сравнению с декодированием по максимуму дискретной функции правдоподобия. 3 ил., 1 табл.

Способ декодирования помехоустойчивых кодов Боуза-Чоудхури-Хоквингема (БЧХ) по методу максимального правдоподобия, заключающийся в приеме сигнала, его обработке и получении последовательности двоичных символов, разбиении принятой последовательности двоичных символов на кодовые слова, перемножении каждого принятого кодового слова на опорную транспонированную матрицу, состоящую из всего множества кодовых слов для данного кода, выборе из полученного множества значений максимального, максимальному значению соответствует переданное слово, отличающийся тем, что после разбиения принятой последовательности двоичных символов на кодовые слова в каждом кодовом слове производят перестановку двоичных символов таким образом, чтобы получить слово, принадлежащее матрице Уолша-Адамара, для определения порядка перестановки символов в кодовом слове и приведения опорной матрицы к матрице Уолша-Адамара, из всего множества кодовых слов составляют матрицу, матрицу разбивают на циркулянты M₁(g(x)), …, M_Z(g(x)) размерности n×n, где n - длина кодового вектора, столбцы каждого циркулянта нумеруют в соответствии с комбинациями-блоками, с которых эти столбцы начинаются, число символов 1 в комбинациях-блоках определяют исходя из соотношения 2¹=n+1, производят перестановку столбцов, располагая их в порядке возрастания номеров столбцов, в результате получают циркулянты порядок перестановки столбцов в циркулянтах определяет порядок перестановки символов в кодовом слове, при перестановке символов в кодовом слове сохраняют соответствие номеров символов в кодовом слове и номеров ячеек регистра слов кода БЧХ, строки каждого из циркулянтов M₁(g(x)), …, M_Z(g(x)) нумеруют в соответствии с 1 двоичными старшими разрядами, полученные номера присваивают строкам циркулянта производят перестановку строк, располагая их таким образом, чтобы после добавления к полученным циркулянтам слева столбца сверху стоки из одних нулей и перевода кодовых элементов в сигнальные получить матрицы Уолша-Адамара, далее кодовое слово, принадлежащее матрице Уолша-Адамара, перемножают с опорными транспонированными матрицами Уолша-Адамара, для получения результата перемножения используют быстрые преобразования Уолша-Адамара, из полученного множества значений (спектра принятого слова) выделяют максимальное, максимальному значению соответствует переданное слово.