Стандартный массив

В теории кодирования стандартный массив (или массив Слепова) — это $q^{n-k}$ к $q^{k}$ массив, в котором перечислены все элементы определенного $\mathbb {F} _{q}^{n}$ векторное пространство . Стандартные массивы используются для декодирования линейных кодов ; т.е. найти соответствующее кодовое слово для любого полученного вектора.

Определение

Стандартный массив для [ n , k ]-кода — это $q^{n-k}$ к $q^{k}$ массив, где:

В первой строке перечислены все кодовые слова (с кодовым словом 0 в крайнем левом углу).
Каждая строка является смежным классом с лидером смежного класса в первом столбце.
Запись в i-й строке и j-м столбце представляет собой сумму i-го лидера смежного класса и j-го кодового слова.

Например, [ 5 , 2 ]-код $C_{3}$ = { 0 , 01101, 10110, 11011} имеет следующий стандартный массив:

0	01101	10110	11011
10000	11101	00110	01011
01000	00101	11110	10011
00100	01001	10010	11111
00010	01111	10100	11001
00001	01100	10111	11010
11000	10101	01110	00011
10001	11100	00111	01010

Вышеупомянутое — это только одна возможность для стандартного массива; если бы 00011 был выбран в качестве первого лидера смежного класса с весом два, был бы создан другой стандартный массив, представляющий код.

Первая строка содержит вектор 0 и кодовые слова $C_{3}$ ( 0 сам по себе является кодовым словом). Кроме того, самый левый столбец содержит векторы минимального веса, сначала перечисляя векторы веса 1, а затем используя векторы веса 2. Кроме того, каждый возможный вектор в векторном пространстве появляется ровно один раз.

Построение стандартного массива

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

Перечислите кодовые слова $C$ , начиная с 0 в качестве первой строки
Выберите любой вектор минимального веса, которого еще нет в массиве. Запишите это как первую запись следующей строки. Этот вектор обозначается как « лидер смежного класса» .
Заполните строку, добавив лидер смежного класса к кодовому слову вверху каждого столбца. Сумма i-го лидера смежного класса и j-го кодового слова становится записью в строке i, столбце j.
Повторяйте шаги 2 и 3, пока все строки/классы не будут перечислены и каждый вектор не появится ровно один раз.

Добавление векторов производится по модулю q. Например, двоичные коды добавляются по модулю 2 (что эквивалентно побитовому сложению XOR). Например, в $Z_{2}$ , 11000 + 11011 = 00011.

Выбор разных лидеров смежных классов создаст немного другой, но эквивалентный стандартный массив и не повлияет на результаты при декодировании.

Пример конструкции

Позволять $C$ — двоичный [4,2]-код. т.е. C = {0000, 1011, 0101, 1110}. Чтобы построить стандартный массив, мы сначала перечисляем кодовые слова подряд.

0000	1011	0101	1110

Затем мы выбираем вектор минимального веса (в данном случае веса 1), который еще не использовался. Этот вектор становится лидером смежного класса для второй строки.

0000	1011	0101	1110
1000

Следуя шагу 3, мы завершаем строку, добавляя лидера смежного класса к каждому кодовому слову.

0000	1011	0101	1110
1000	0011	1101	0110

Затем повторяем шаги 2 и 3, пока не закончим все ряды. Мы останавливаемся, когда достигаем $q^{n-k}=2^{4-2}=2^{2}=4$ ряды.

0000	1011	0101	1110
1000	0011	1101	0110
0100	1111	0001	1010
0010	1001	0111	1100

В этом примере мы не могли выбрать вектор 0001 в качестве лидера смежного класса последней строки, даже если он соответствует критерию минимального веса (1), поскольку вектор уже присутствовал в массиве. Однако мы могли бы выбрать его в качестве лидера первого смежного класса и построить другой стандартный массив.

Декодирование через стандартный массив

Чтобы декодировать вектор с использованием стандартного массива, вычтите вектор ошибки (или лидер смежного класса) из полученного вектора. Результатом будет одно из кодовых слов в $C$ . Например, предположим, что мы используем код C = {0000, 1011, 0101, 1110} и создали соответствующий стандартный массив, как показано в примере выше. Если мы получим вектор 0110 как сообщение, мы найдем этот вектор в стандартном массиве. Затем мы вычитаем лидера смежного класса вектора, а именно 1000, чтобы получить результат 1110. Мы получили кодовое слово 1110.

Декодирование через стандартный массив является формой декодирования ближайшего соседа . На практике декодирование через стандартный массив требует больших объемов памяти — код с 32 кодовыми словами требует стандартного массива с $2^{32}$ записи. Другие формы декодирования, такие как синдромное декодирование , более эффективны.

Декодирование с помощью стандартного массива не гарантирует, что все векторы будут декодированы правильно. Если мы получим вектор 1010, использование приведенного выше стандартного массива приведет к декодированию сообщения как 1110, на расстоянии 1 кодового слова. Однако 1010 также находится на расстоянии 1 от кодового слова 1011. В таком случае некоторые реализации могут запросить повторную отправку сообщения, или неоднозначный бит может быть помечен как стираемый, и следующий внешний код может его исправить. Эта неоднозначность является еще одной причиной того, что иногда используются разные методы декодирования.

См. также

Линейный код

Ссылки

Хилл, Раймонд (1986). Первый курс теории кодирования . Оксфордская серия «Прикладная математика и информатика». Издательство Оксфордского университета . ISBN 978-0-19-853803-5 .