Блочный код это:

Блочный код

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

Главная характеристика блочного кода состоит в том, что это – канальный код фиксированной длины (в отличие от такой схемы кодирования источника данных, как кодирование Хаффмана, и в отличие таких методов канального кодирования, как конволюционное кодирование («сверточное» кодирование) ). Обычно, система блочного кодирования получает на входе 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.

Wikimedia Foundation. 2010.

Смотреть что такое "Блочный код" в других словарях:

  • блочный код — Множество всех кодовых слов, возможных при данном способе блочного кодирования. [Сборник рекомендуемых терминов. Выпуск 94. Теория передачи информации. Академия наук СССР. Комитет технической терминологии. 1979 г.] Тематики теория передачи… …   Справочник технического переводчика

  • блочный код — Код, взаимно однозначно сопоставляющий каждый элемент сообщения конечному числу (блоку) символов …   Политехнический терминологический толковый словарь

  • блочный код с неизменной длиной — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN fixed length code …   Справочник технического переводчика

  • код с исправлением ошибок Рида-Соломона — Линейный блочный код с исправлением ошибок, применяемый для исправления ошибок, которые могут возникнуть в штриховых или матричных кодах при стирании или удалении части символа. Примечания 1. Линейный код код, кодирование и декодирование которого …   Справочник технического переводчика

  • Линейный код — В области математики и теории информации линейный код  это важный тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы… …   Википедия

  • неравномерный код — Блочный код, в котором имеются слова различной длины. [Сборник рекомендуемых терминов. Выпуск 94. Теория передачи информации. Академия наук СССР. Комитет технической терминологии. 1979 г.] Тематики теория передачи информации EN variable length… …   Справочник технического переводчика

  • несовершенный код — Блочный код, выбираемый из ансамбля, в котором различные кодовые слова обеспечивают не одинаковую степень защиты от помех, а число исправляемых ошибок зависит от вида кодовой комбинации. [Л.М. Невдяев. Телекоммуникационные технологии. Англо… …   Справочник технического переводчика

  • равномерный код — Блочный код, все слова которого имеют одну и ту же длину. [Сборник рекомендуемых терминов. Выпуск 94. Теория передачи информации. Академия наук СССР. Комитет технической терминологии. 1979 г.] Тематики теория передачи информации EN fixed length… …   Справочник технического переводчика

  • совершенный код — Блочный код (n, k), в котором число исправляемых ошибок одинаково и не зависит от вида кодовой комбинации. Ср. imperfect . [Л.М. Невдяев. Телекоммуникационные технологии. Англо русский толковый словарь справочник. Под редакцией Ю.М. Горностаева.… …   Справочник технического переводчика

  • расстояние Хемминга — хемминговское расстояние Расстояние d (u,v) между двумя кодовыми последовательноаями u и v одинаковой длины, равное числу символов, в которых они отличаются. Блочный код с минимальным хемминговским расстоянием d позволяет обнаружить (d 1) и… …   Справочник технического переводчика


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»