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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Линейный код

• Хилл, Рэймонд (1986). Первый курс теории кодирования . Серия Oxford Applied Mathematics and Computing Science. Oxford University Press . ISBN 978-0-19-853803-5.