Блочный код

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

Главная характеристика блочного кода состоит в том, что это – канальный код фиксированной длины (в отличие от такой схемы кодирования источника данных, как кодирование Хаффмана, и в отличие таких методов канального кодирования, как конволюционное кодирование («сверточное» кодирование) ). Обычно, система блочного кодирования получает на входе k-значное кодовое слово W, и преобразовывает его в n-значное кодовое слово C(W). Это кодовое слово и называется блоком.

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

Формальное определение

Блочный код - код, кодирующий последовательности из набора символов алфавита S в кодовые слова, преобразуя каждый символ из S отдельно. Пусть $(k_1,k_2,\ldots,k_m)$ - последовательность натуральных чисел, каждое меньше |S|. Если $S=\{s_1,s_2,\ldots,s_n\}$ и некоторое слово W из алфавита S записано как $W=s_{k_1}s_{k_2}\ldots s_{k_m}$, тогда кодовым словом, соответствующим W, а именно, C(W), будет: $C(W) = C(s_{k_1})C(s_{k_2})\ldots C(s_{k_m})$ .

[n, d]

Компромисс между эффективностью (большей скоростью передачи информации) и способностями исправления может также быть виден при попытке задать фиксированную длину ключевого слова, и фиксированную возможность исправления (представленную расстоянием Хемминга d) и максимизируют общее количество ключевых слов. [n, d] — максимальное число ключевых слов для данной длины ключевого слова n и расстояния Хемминга d.

Информационные нормы

Когда C - двойной блочный код, состоящий из А ключевых слов длиной n бит, тогда информационная норма C определяется как:

$\frac{\!log_{2}(A)}{n}$.

В случае, когда первые k бит ключевого слова - независимые информационные биты, то информационная норма будет иметь вид:

$\frac{\!log_{2}(2^k)}{n}=\frac{k}{n}$.

Сферические упаковки и решетки

Блочные коды связаны с проблемой сферической упаковки, которая привлекла к себе внимания в последние годы. В двух измерениях её легко визуализировать, взяв горсть одинаковых монет и выстроив их на столе в виде шестиугольника, как в пчелиных сотах. Однако, блочные коды в больших измерениях также легко визуализировать не удастся. Сильный код Голея, используемый в коммуникациях открытого космоса, использует 24 измерения. Если используется двоичный код (как это обычно и делается) измерения обращаются к длине ключевого слова как определено выше.

Теория кодирования использует модель N-мерной сферы. Например, сколько монет может быть уложено в круг на поверхности стола или в 3 измерениях, сколько мрамора может быть помещено в земной шар. Другие рассмотрения входят в выбор кода. Например, шестиугольник, помещенный в ограниченную прямоугольную коробку, оставит пустое место в углах. Поскольку измерения увеличиваются, процент от пустого места становится меньшим. Но в определенных измерениях заполняется все место и эти коды - так называемые совершенные коды. Но их очень мало.

Другим пунктом, который часто пропускается, является число соседей, которых может иметь единственное ключевое слово. Снова, давайте использовать монеты как пример. Сначала мы укладываем их в прямоугольной сетке. У каждой монеты будет 4 близких соседа (и 4 в наиболее удаленных углах). В шестиугольнике у каждой монеты будет 6 близких соседей. Когда мы увеличиваем количество измерений, число близких соседей растет очень быстро.

Результат – также рост числа путей, когда шум вынуждал бы получателя выбрать соседа, (следовательно - ошибка). Это - фундаментальное ограничение блочных кодов, и действительно всех кодов. Может быть единственному соседу тяжелее вызвать ошибку, но число соседей может быть достаточно большим, таким образом полная ошибочная вероятность фактически возможна.

Литература

• J. H van Lint (1992). Введение в Теорию Кодирования. GTM. 86 (2-е издание). Springer-Verlag. p. 31. ISBN 3-540-54894-7.
• F. J. MacWilliams; N.J.A. Sloane (1977). Теория кодов, исправляющих ошибки. Северная Голландия. p. 35. ISBN 0-444-85193-3.

Связать^?

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