Блочный код

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Формальное определение[править | править код]

Блочный код — код, кодирующий последовательности из набора символов алфавита S в кодовые слова, преобразуя каждый символ из S отдельно. Пусть  — последовательность натуральных чисел, каждое меньше |S|. Если и некоторое слово W из алфавита S записано как , тогда кодовым словом, соответствующим W, а именно, C(W), будет: .

[n, d][править | править код]

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

Информационные нормы[править | править код]

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

.

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

.

Сферические упаковки и решётки[править | править код]

Блочные коды связаны с проблемой сферической упаковки, которая привлекла к себе внимания в последние годы. В двух измерениях её легко визуализировать, взяв горсть одинаковых монет и выстроив их на столе в виде шестиугольника, как в пчелиных сотах. Однако в больших измерениях блочные коды не удаётся визуализировать так же легко. Сильный код Голея, используемый в коммуникациях открытого космоса, использует 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.
  • Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. Изд. "Мир", 1976.