О ОПРЕДЕЛЕНИИ ПАРАМЕТРОВ ЛИНЕЙНЫХ КОДОВ

​ON DETERMINATION OF PARAMETERS OF LINEAR CODES

Eleonora Guliaeva

master's student, Department of Automation, Novosibirsk State Technical University,

Russia, Novosibirsk

Denis Katasonov

scientific supervisor, candidate of Technical Sciences, associate professor, Novosibirsk State Technical University,

Russia, Novosibirsk

АННОТАЦИЯ

Рассматривается вычислительная трудоемкость алгоритмов оценки истинного кодового расстояния линейного кода.

ABSTRACT

The computational complexity of algorithms for estimating the true code distance of a linear code is considered.

Ключевые слова: линейный код; кодовое расстояние; проверочная матрица.

Keywords: linear code; hamming distance; check matrix.

Помехоустойчивое кодирование является одним из способов борьбы с искажениями хранимых и передаваемых данных. В настоящее время наиболее распространенным классом кодов являются линейные коды, такие коды характеризуются тем, что любое слово принадлежащая коду может быть представлено, как линейная комбинация других слов также принадлежащих этому коду. Среди линейных кодов наиболее распространены так называемых циклические коды, для которых существуют эффективные способы построения. Наиболее распространенной возможностью построения циклического кода является построение так называемого БЧХ кода [1]. Помимо БЧХ кодов существует обширная таблица циклических кодов приведенная в [2]. Кроме этого, существует ряд источников содержащих описание порождающих полиномов циклических кодов, параметры которых достоверно не известны или приведены оценочные величины. В настоящей работе рассматриваются различные способы определения истинного кодового расстояния с точки зрения вычислительной трудоемкости.

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

Наиболее очевидным и простым способом является анализ разрешенных кодовых комбинаций. В основе данного метода лежит перебор, в ходе которого происходит сравнений всех возможных пар комбинаций, количество которых определяется мощностью кода M = qk, где k определяет число информационных разрядов. Несколько оптимизировать такой способ возможно следующим образом. Пусть разрешенные комбинации сохранены в некотором массиве размерностью M, каждую комбинацию обозначим как ai, где i – индекс комбинации в массиве и может изменяться в пределах [1;M]. Для комбинации ai пары для сравнения будут выбраны из комбинаций индексы которых находятся в пределах [i+1; M].

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

Также к «синдромным» способам можно отнести поиск наборов линейно независимых наборов столбцов проверочной матрицы, этот способ подразумевает формирование различных сочетаний столбцов, поразрядное суммирование которых приводит к нулевому столбцу.

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

                                                                                                 (1)

 – вектор-строка кодируемого слова;

 – порождающая матрица кода длины n c количеством информационных разрядов k.

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

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

                                                                                            (2)

S – синдром ошибки вектора v;

  –­ проверочная матрица.

Расчет синдрома требует вычислений. Переводом синдрома в число без знака пренебрежём. Таким образом, на каждую пару синдромов требуется  вычислений, за единицу примем операцию сравнения значений синдромов. Процедура поиска равных синдромов может быть остановлена при кратности ошибки равной единице или останов может произойти при приближении к верхней границе кодового расстояния.  Предельное количество синдромов будет равно , где  – предельное число исправляемых ошибок, определенное при помощи оценки Хэмминга,  – число сочетаний. Общее количество сравниваемых пар синдромов определяется, как в случае перебора разрешенных комбинаций и равно . Таким образом, в худшем случае, количество вычислений будет равно .

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

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

Сравним вычислительную сложность рассмотренных алгоритмов на примере кодов длины 15 и 31, построим зависимости скорости кода и количества вычислительных операций для каждого из рассмотренных способов. При этом, вычислительная сложность всех рассмотренных способов, кроме анализа разрешенных комбинаций, зависит от истинного кодового расстояния кода. Иначе говоря, процедура определения кодового расстояния может быть остановлена до достижения предельного оценочного значения кодового расстояния. Исходя из этого, рассмотрим два случая – предельное количество вычислений, необходимое, при приближении к верхней границе кодового расстояния, и объема вычислений потребовавшегося при выполнении вычислительного эксперимента. На рисунке 1 показан предельный случай, при котором рассматривается верхняя граница кодового расстояния.

Рисунок 1. Зависимость числа переборов от скорости кода, при длине кода n = 1. Случай А – случай приближения к верхней границе кодового расстояния, В – случай истинного кодового расстояния.

На рисунке 1 показана зависимость числа переборов от скорости кода, при длине кода равной 15. Как видно из приведенных графиков, при скорости кода до 0.5 эффективным оказывается способ разрешенных кодовых комбинаций, после чего более эффективным оказывается матричный метод. Матричный метод, в случае приближения к верхней границе кодового расстояния фактически имеет константное количество вычислений. Аналогичные результаты были получены для кодов длины 31, при аналогичных значениях скорости.

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

Рисунок 2. Анализ разрешенных кодовых комбинаций. ai – очередная комбинация, M – мощность кода.

На рисунке 2 схематично показан массив, хранящий разрешенные кодовые комбинации. Сравнение пар происходит следующим образом. Для комбинации a1 осуществляется сравнение с комбинациями a2…aM, для комбинации a2 происходит сравнение с a3…aM и так далее. Осуществить параллельное вычисление возможно, если разделить массив на фрагменты, как схематично показано стрелками на рисунке 2, таким образом, первый поток начинает сравнение с комбинации a1, второй поток с комбинации a3.

Определение кодового расстояния методом поиска совпадения синдромов осуществляется аналогичным образом, только вместо определения кодового расстояния между парами комбинаций происходит их сравнение. Подготовка синдромов может быть осуществлена параллельно – первый поток осуществляет расчет для ошибки кратности один, второй для кратности два и т.д. Поиск нулевого синдрома осуществляется аналогично. Матричный метод подразумевает предварительное формирование возможных комбинаций столбцов, после чего сложение групп столбцов может быть осуществлено параллельно. На рисунке 3 приведен сравнительный анализ времени выполнения анализа разрешенных комбинаций, в случае кодов длины 15.

Рисунок 3. Зависимость времени выполнения от мощности кода при разном числе потоков.

Как видно из рисунка 3, до мощности кода равной 128 прироста производительности от увеличения числа потоков не происходит, это связано с дополнительными накладными расходами необходимыми для запуска и контроля нескольких потоков, использования мьютексов. Эксперимент производился с использованием средств библиотеки std. Аналогичные результаты достигаются при использовании других методов.

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

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

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

1. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М: Мир, 1986. — 576 с.
2. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976. — 575 с.