В теории кодирования , а стандартный массив (или Слепяна массив) является от массив, в котором перечислены все элементы определенного векторное пространство . Стандартные массивы используются для декодирования линейных кодов ; т.е. найти соответствующее кодовое слово для любого полученного вектора.
Определение
Стандартный массив для [ n , k ] -кода - это от массив где:
- В первой строке перечислены все кодовые слова (с кодовым словом 0 в крайнем левом углу).
- Каждая строка является смежным классом с лидером смежного класса в первом столбце.
- Запись в i-й строке и j-м столбце является суммой i-го лидера смежного класса и j-го кодового слова.
Например, [ 5 , 2 ] -код= { 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 и кодовые слова( 0 само по себе является кодовым словом). Кроме того, крайний левый столбец содержит векторы минимального веса, сначала перечисляя векторы веса 1, а затем используя векторы веса 2. Также каждый возможный вектор в векторном пространстве появляется ровно один раз.
Построение стандартного массива
Поскольку каждый возможный вектор может появляться в стандартном массиве только один раз, при построении необходимо соблюдать осторожность. Стандартный массив можно создать следующим образом:
- Перечислите кодовые слова , начиная с 0 , как первая строка
- Выберите любой вектор минимального веса, которого еще нет в массиве. Запишите это как первую запись следующей строки. Этот вектор обозначается как « лидер смежного класса» .
- Заполните строку, добавив лидера смежного класса к кодовому слову вверху каждого столбца. Сумма i-го лидера смежного класса и j-го кодового слова становится записью в строке i, столбце j.
- Повторяйте шаги 2 и 3, пока не будут перечислены все строки / смежные классы, и каждый вектор не появится ровно один раз.
Добавление векторов выполняется по модулю q. Например, двоичные коды добавляются по модулю 2 (что эквивалентно поразрядному сложению XOR). Например, в, 11000 + 11011 = 00011.
Выбор разных лидеров смежного класса создаст немного другой, но эквивалентный стандартный массив и не повлияет на результаты при декодировании.
Пример конструкции
Позволять быть двоичным [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, пока не завершим все ряды. Мы останавливаемся, когда достигли ряды.
0000 | 1011 | 0101 | 1110 |
1000 | 0011 | 1101 | 0110 |
0100 | 1111 | 0001 | 1010 |
0010 | 1001 | 0111 | 1100 |
В этом примере мы не могли выбрать вектор 0001 в качестве лидера смежного класса последней строки, даже если он соответствует критерию минимального веса (1), потому что вектор уже присутствовал в массиве. Однако мы могли бы выбрать его в качестве первого лидера смежного класса и построить другой стандартный массив.
Расшифровка стандартным массивом
Чтобы декодировать вектор с помощью стандартного массива, вычтите вектор ошибок - или лидера смежного класса - из полученного вектора. Результатом будет одно из кодовых слов в. Например, предположим, что мы используем код C = {0000, 1011, 0101, 1110} и построили соответствующий стандартный массив, как показано в примере выше. Если мы получаем вектор 0110 как сообщение, мы находим этот вектор в стандартном массиве. Затем мы вычитаем лидера смежного класса вектора, а именно 1000, чтобы получить результат 1110. Мы получили кодовое слово 1110.
Декодирование с помощью стандартного массива - это форма декодирования ближайшего соседа . На практике для декодирования с помощью стандартного массива требуется большой объем памяти - для кода с 32 кодовыми словами требуется стандартный массив сзаписи. Другие формы декодирования, такие как декодирование синдрома , более эффективны.
Декодирование с помощью стандартного массива не гарантирует правильного декодирования всех векторов. Если мы получим вектор 1010, использование стандартного массива выше расшифрует сообщение как 1110, расстояние кодового слова равно 1. Однако 1010 также находится на расстоянии 1 от кодового слова 1011. В таком случае некоторые реализации могут запрашивать повторную отправку сообщения, или неоднозначный бит может быть помечен как стирание, и следующий внешний код может исправить его. Эта неоднозначность - еще одна причина того, что иногда используются разные методы декодирования.
Смотрите также
Рекомендации
- Хилл, Раймонд (1986). Первый курс теории кодирования . Серия Oxford Applied Mathematics and Computing Science. Издательство Оксфордского университета . ISBN 978-0-19-853803-5.