Блочный код

редактировать

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

Примеры блочных кодов: коды Рида – Соломона, коды Хэмминга, коды Адамара, коды расширителей, коды Голея и коды Рида – Маллера. Эти примеры также принадлежат к классу линейных кодов, и поэтому они называются линейными блочными кодами . В частности, эти коды известны как алгебраические блочные коды или циклические блочные коды, потому что они могут быть сгенерированы с использованием логических полиномов.

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

Термин блочный код может также относиться к любому коду с исправлением ошибок, который действует на блок $k {\ displaystyle k}$ $k$ битов входных данных для создания $n {\ displaystyle n}$ $n$ битов выходных данных $(n, k) {\ displaystyle (n, k)}$ $(n, k)$ . Следовательно, блочный кодер - это устройство без памяти. В соответствии с этим определением коды, такие как турбокоды, сверточные коды с завершением и другие итеративно декодируемые коды (турбоподобные коды), также будут считаться блочными кодами. Сверточный кодер без завершения может быть примером неблочного (без кадра) кода, который имеет память и вместо этого классифицируется как древовидный код.

В этой статье рассматриваются «алгебраические блочные коды».

Содержание

1 Код блока и его параметры
- 1.1 Алфавит Σ
- 1.2 Длина сообщения k
- 1.3 Длина блока n
- 1.4 Скорость R
- 1.5 Расстояние d
- 1.6 Популярные обозначения
2 Примеры
3 Свойства обнаружения и исправления ошибок
4 Нижняя и верхняя границы блочных кодов
- 4.1 Семейство кодов
- 4.2 Граница Хэмминга
- 4.3 Синглтон граница
- 4.4 Граница Плоткина
- 4.5 Граница Гилберта – Варшамова
- 4.6 Граница Джонсона
- 4.7 Граница Элиаса – Бассалиго
5 Сферические упаковки и решетки
6 См. также
7 Ссылки
8 Внешние ссылки

Код блока и его параметры

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

Формально, блочный код - это инъективное отображение

C: Σ k → Σ n {\ displaystyle C: \ Sigma ^ {k} \ to \ Sigma ^ {n} }

C: \ Sigma ^ {k} \ to \ Sigma ^ {n}

Здесь $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ - конечное и непустое множество и $k {\ displaystyle k}$ $k$ и $n {\ displaystyle n}$ $n$ - целые числа. Значение и значение этих трех параметров и других параметров, связанных с кодом, описаны ниже.

Алфавит Σ

Кодируемый поток данных моделируется как строка над некоторым алфавитом $Σ {\ displaystyle \ Sigma }$ $\ Sigma$ . Размер $| Σ | {\ displaystyle | \ Sigma |}$ $| \ Sigma |$ алфавита часто записывается как $q {\ displaystyle q}$ $q$ . Если $q = 2 {\ displaystyle q = 2}$ $q = 2$ , то блочный код называется двоичным блочным кодом. Во многих приложениях полезно рассматривать $q {\ displaystyle q}$ $q$ как простую степень и определять $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ с конечным полем $F q {\ displaystyle \ mathbb {F} _ {q}}$ $\ mathbb {F} _ {q}$ .

Длина сообщения k

Сообщения являются элементами $m {\ displaystyle m}$ $m$ из $Σ k {\ displaystyle \ Sigma ^ {k}}$ $\ Sigma ^ {k}$ , то есть строки длиной $k {\ displaystyle k }$ $k$ . Следовательно, число $k {\ displaystyle k}$ $k$ называется длиной сообщения или размером блочного кода.

Длина блока n

Длина блока $n {\ displaystyle n}$ $n$ блочного кода - это количество символов в Блок. Следовательно, элементы $c {\ displaystyle c}$ $c$ из $Σ n {\ displaystyle \ Sigma ^ {n}}$ $\ Сигма ^ {n}$ представляют собой строки длины $n { \ displaystyle n}$ $n$ и соответствуют блокам, которые могут быть получены получателем. Поэтому их еще называют принятыми словами. Если $c = C (m) {\ displaystyle c = C (m)}$ $c = C (m)$ для некоторого сообщения $m {\ displaystyle m}$ $m$ , то $c {\ displaystyle c}$ $c$ называется кодовым словом $m {\ displaystyle m}$ $m$ .

Скорость R

rate блочного кода определяется как отношение длины сообщения к длине блока:

R = k / n {\ displaystyle R = k / n}

R = k / n

Большая скорость означает, что количество фактического сообщения на переданный блок велико. В этом смысле скорость измеряет скорость передачи, а величина $1 - R {\ displaystyle 1-R}$ $1-R$ измеряет накладные расходы, возникающие из-за кодирования с помощью блочного кода. Это простой теоретический факт, что скорость не может превышать $1 {\ displaystyle 1}$ $1$ , поскольку данные, как правило, не могут быть сжаты без потерь. Формально это следует из того факта, что код $C {\ displaystyle C}$ $C$ является инъективным отображением.

Расстояние d

расстояние или минимальное расстояние d блочного кода - это минимальное количество позиций, в которых любые два отдельных кодовых слова отличаются, а относительное расстояние $δ {\ displaystyle \ delta}$ $\ delta$ - это дробь $d / n {\ displaystyle d / n}$ $d / n$ . Формально для полученных слов $c 1, c 2 ∈ Σ n {\ displaystyle c_ {1}, c_ {2} \ in \ Sigma ^ {n}}$ $c_ {1}, c_ {2} \ in \ Sigma ^ {n}$ , пусть $Δ ( c 1, c 2) {\ displaystyle \ Delta (c_ {1}, c_ {2})}$ $\ Delta ( c_ {1}, c_ {2})$ обозначают расстояние Хэмминга между $c 1 {\ displaystyle c_ { 1}}$ $c_ {1}$ и $c 2 {\ displaystyle c_ {2}}$ $c_ {2}$ , то есть количество позиций, в которых $c 1 {\ displaystyle c_ {1 }}$ $c_ {1}$ и $c 2 {\ displaystyle c_ {2}}$ $c_ {2}$ различаются. Тогда минимальное расстояние $d {\ displaystyle d}$ $d$ кода $C {\ displaystyle C}$ $C$ определяется как

d: = min m 1, м 2 ∈ Σ км 1 ≠ м 2 Δ [С (м 1), С (м 2)] {\ displaystyle d: = \ min _ {m_ {1}, m_ {2} \ in \ Sigma ^ {k} \ atop m_ {1} \ neq m_ {2}} \ Delta [C (m_ {1}), C (m_ {2})]}

{\ displaystyle d: = \ min _ {m_ {1}, m_ {2} \ in \ Sigma ^ {k} \ на вершине m_ {1} \ neq m_ {2}} \ Delta [C (m_ {1}), C (m_ {2})]}

Поскольку любой код должен быть инъективным, любые два кодовых слова не совпадают по крайней мере в одной позиции, поэтому расстояние любого кода составляет не менее $1 {\ displaystyle 1}$ $1$ . Кроме того, расстояние равно минимальному весу для линейных блочных кодов, потому что:

min m 1, m 2 ∈ Σ km 1 ≠ m 2 Δ [ C (m 1), C (m 2)] = min m 1, m 2 ∈ Σ km 1 ≠ m 2 Δ [0, C (m 1) + C (m 2)] = min m ∈ Σ km ≠ 0 вес [C (m)] = w min {\ displaystyle \ min _ {m_ {1}, m_ {2} \ in \ Sigma ^ {k} \ на вершине m_ {1} \ neq m_ {2}} \ Delta [ C (m_ {1}), C (m_ {2})] = \ min _ {m_ {1}, m_ {2} \ in \ Sigma ^ {k} \ atop m_ {1} \ neq m_ {2} } \ Delta [\ mathbf {0}, C (m_ {1}) + C (m_ {2})] = \ min _ {m \ in \ Sigma ^ {k} \ atop m \ neq \ mathbf {0} } w [C (m)] = w _ {\ min}}

{\ displaystyle \ min _ {m_ {1}, m_ {2} \ in \ Sigma ^ {k} \ на вершине m_ {1} \ neq m_ {2 }} \ Delta [C (m_ {1}), C (m_ {2})] = \ min _ {m_ {1}, m_ {2} \ in \ Sigma ^ {k} \ atop m_ {1} \ п eq m_ {2}} \ Delta [\ mathbf {0}, C (m_ {1}) + C (m_ {2})] = \ min _ {m \ in \ Sigma ^ {k} \ atop m \ neq \ mathbf {0}} w [C (m)] = w _ {\ min}}

Чем больше расстояние, тем больше ошибок исправляется и обнаруживается. Например, если мы рассматриваем только ошибки, которые могут изменить символы отправленного кодового слова, но никогда не стираем и не добавляем их, то количество ошибок - это количество позиций, в которых отправленное кодовое слово и полученное слово отличаются. Код с расстоянием d позволяет приемнику обнаруживать до $d - 1 {\ displaystyle d-1}$ $d-1$ ошибок передачи после изменения $d - 1 {\ displaystyle d-1}$ $d-1$ позиции кодового слова никогда не могут случайно дать другое кодовое слово. Кроме того, если возникает не более $(d - 1) / 2 {\ displaystyle (d-1) / 2}$ $(d-1) / 2$ ошибок передачи, приемник может однозначно декодировать полученное слово в кодовое слово. Это связано с тем, что каждое полученное слово имеет не более одного кодового слова на расстоянии $(d - 1) / 2 {\ displaystyle (d-1) / 2}$ $(d-1) / 2$ . Если возникает больше чем $(d - 1) / 2 {\ displaystyle (d-1) / 2}$ $(d-1) / 2$ ошибок передачи, приемник не может однозначно декодировать полученное слово в целом, так как может быть несколько возможных кодовые слова. Один из способов для приемника справиться с этой ситуацией состоит в использовании декодирования списка, при котором декодер выводит список всех кодовых слов в определенном радиусе.

Популярное обозначение

Обозначение $(n, k, d) q {\ displaystyle (n, k, d) _ {q}}$ $(n, k, d) _ {q}$ описывает блочный код над алфавитом $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ размером $q {\ displaystyle q}$ $q$ с длиной блока $n {\ displaystyle n}$ $n$ , длина сообщения $k {\ displaystyle k}$ $k$ и расстояние $d {\ displaystyle d}$ $d$ . Если блочный код является линейным блочным кодом, тогда квадратные скобки в обозначении $[n, k, d] q {\ displaystyle [n, k, d] _ {q}}$ $[n, k, d] _ {q}$ являются используется для представления этого факта. Для двоичных кодов с $q = 2 {\ displaystyle q = 2}$ $q = 2$ индекс иногда опускается. Для разделяемых кодов максимального расстояния расстояние всегда равно $d = n - k + 1 {\ displaystyle d = n-k + 1}$ $d=n-k+1$ , но иногда точное расстояние равно не известно, нетривиально доказать или заявить, или не нужно. В таких случаях компонент $d {\ displaystyle d}$ $d$ может отсутствовать.

Иногда, особенно для неблочных кодов, используется запись $(n, M, d) q {\ displaystyle (n, M, d) _ {q}}$ $(n, M, d) _ {q}$ используется для кодов, содержащих $M {\ displaystyle M}$ $M$ кодовые слова длины $n {\ displaystyle n}$ $n$ . Для блочных кодов с сообщениями длины $k {\ displaystyle k}$ $k$ по алфавиту размера $q {\ displaystyle q}$ $q$ это число будет $M = qk {\ displaystyle M = q ^ {k}}$ $M = q ^ {k}$ .

Примеры

Как упоминалось выше, существует огромное количество кодов с исправлением ошибок, которые на самом деле являются блочными кодами. Первым исправляющим ошибки кодом был код Хэмминга (7,4), разработанный Ричардом У. Хэммингом в 1950 году. Этот код преобразует сообщение, состоящее из 4 бит, в кодовое слово 7 бит, добавив 3 бита четности. Следовательно, этот код является блочным кодом. Оказывается, это также линейный код и расстояние 3. В сокращенной записи выше это означает, что код Хэмминга (7,4) - это $[7, 4, 3] 2 {\ displaystyle [7,4,3] _ {2}}$ $[7,4,3] _ {2}$ код.

Коды Рида – Соломона представляют собой семейство кодов $[n, k, d] q {\ displaystyle [n, k, d] _ {q}}$ $[n, k, d] _ {q}$ с $d = n - k + 1 {\ displaystyle d = n-k + 1}$ $d=n-k+1$ и $q {\ displaystyle q}$ $q$ является степенью простого числа. Коды ранга - это семейство кодов $[n, k, d] q {\ displaystyle [n, k, d] _ {q}}$ $[n, k, d] _ {q}$ с $d ≤ n - k + 1 {\ displaystyle d \ leq n-k + 1}$ $d \ leq n-k + 1$ . коды Адамара представляют собой семейство $[n, k, d] 2 {\ displaystyle [n, k, d] _ {2}}$ $[ n, k, d] _ {2}$ коды с $n = 2 k - 1 {\ displaystyle n = 2 ^ {k-1}}$ $n = 2 ^ {k-1}$ и $d = 2 k - 2 {\ displaystyle d = 2 ^ {k-2}}$ $d = 2 ^ {k-2}$ .

Свойства обнаружения и исправления ошибок

Кодовое слово $c ∈ Σ n {\ displaystyle c \ in \ Sigma ^ {n}}$ $с \ in \ Sigma ^ {n}$ можно рассматривать как точку в $n {\ displaystyle n}$ $n$ -размерном пространстве $Σ n {\ displaystyle \ Sigma ^ {n}}$ $\ Сигма ^ {n}$ , а код $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ является подмножеством $Σ n {\ displaystyle \ Sigma ^ {n}}$ $\ Сигма ^ {n}$ . Код $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ имеет расстояние $d {\ displaystyle d}$ $d$ означает, что $∀ c ∈ C { \ displaystyle \ forall c \ in {\ mathcal {C}}}$ $\ forall c \ in {\ mathcal {C}}$ , в шаре Хэмминга нет другого кодового слова с центром в $c {\ displaystyle c}$ $c$ с радиусом $d - 1 {\ displaystyle d-1}$ $d-1$ , который определяется как набор слов размерности $n {\ displaystyle n}$ $n$ , которых расстояние от до $c {\ displaystyle c}$ $c$ не превышает $d - 1 {\ displaystyle d-1}$ $d-1$ . Точно так же $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ с (минимальным) расстоянием $d {\ displaystyle d}$ $d$ имеет следующие свойства:

$C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ может обнаруживать $d - 1 {\ displaystyle d-1}$ $d-1$ ошибки: потому что кодовое слово $c { \ displaystyle c}$ $c$ - единственное кодовое слово в шаре Хэмминга с центром в самом себе с радиусом $d - 1 {\ displaystyle d-1}$ $d-1$ , шаблон ошибок $отсутствует d - 1 {\ displaystyle d-1}$ $d-1$ или меньше ошибок могут изменить одно кодовое слово на другое. Когда получатель обнаруживает, что полученный вектор не является кодовым словом $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ , ошибки обнаруживаются (но нет гарантии исправления).
$C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ может исправить $⌊ d - 1 2 ⌋ {\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$ $\ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor$ ошибки. Поскольку кодовое слово $c {\ displaystyle c}$ $c$ является единственным кодовым словом в шаре Хэмминга с центром в самом себе с радиусом $d - 1 {\ displaystyle d-1}$ $d-1$ , два шара Хэмминга с центрами в двух разных кодовых словах соответственно с радиусом $⌊ d - 1 2 ⌋ {\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$ $\ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor$ не пересекаются друг с другом. Следовательно, если мы рассматриваем исправление ошибок как поиск кодового слова, ближайшего к принятому слову $y {\ displaystyle y}$ $y$ , пока количество ошибок не превышает $⌊ d - 1 2 ⌋ {\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$ $\ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor$ , в шаре Хэмминга есть только одно кодовое слово с центром в $y { \ displaystyle y}$ $y$ с радиусом $⌊ d - 1 2 ⌋ {\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$ $\ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor$ , поэтому все ошибки можно исправить.
Для декодирования при наличии более $(d - 1) / 2 {\ displaystyle (d-1) / 2}$ $(d-1) / 2$ ошибок, декодирование списка или декодирование максимального правдоподобия можно использовать.
$C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ может исправить $d - 1 {\ displaystyle d-1}$ $d-1$ стирает. Под стиранием это означает, что положение стертого символа известно. Исправление может быть выполнено с помощью $q {\ displaystyle q}$ $q$ -проходного декодирования: в $iith {\ displaystyle i ^ {th}}$ $i ^ {th}$ при передаче стертой позиции заполняется с символом $ith {\ displaystyle i ^ {th}}$ $i ^ {th}$ и выполняется исправление ошибок. Должна быть одна передача, что количество ошибок не превышает $⌊ d - 1 2 ⌋ {\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$ $\ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor$ и, следовательно, стирания могут быть исправлены.

Нижняя и верхняя границы блочных кодов

Предел Хэмминга

Существуют теоретические пределы (например, предел Хэмминга), но другой вопрос заключается в том, какие коды могут фактически быть построены. Это похоже на упаковку сфер в коробку во многих измерениях. Эта диаграмма показывает конструктивные коды, которые являются линейными и двоичными. Ось x показывает количество защищенных символов k, ось y - количество необходимых контрольных символов n – k. На графике показаны пределы для различных расстояний Хэмминга от 1 (незащищенный) до 34. Точками отмечены точные коды:

светло-оранжевый по оси x: тривиальные незащищенные коды
оранжевый по оси y: тривиальные повторяющиеся коды
темно-оранжевый на наборе данных d = 3: классические совершенные коды Хэмминга
темно-красный и больше: единственный идеальный двоичный код Голея

Семейство кодов

$C = {C i} я ≥ 1 {\ displaystyle C = \ {C_ {i} \} _ {i \ geq 1}}$ $C = \ {C_ {i} \} _ {i \ geq 1}$ называется семейством кодов, где $C i {\ displaystyle C_ {i}}$ $C_ { i}$ - это код $(ni, ki, di) q {\ displaystyle (n_ {i}, k_ {i}, d_ {i}) _ {q}}$ $(n_ {i}, k_ {i}, d_ {i}) _ {q}$ с монотонным увеличением $ni {\ displaystyle n_ {i}}$ $n_{i}$ .

Скорость семейства кодов C определяется как $R (C) = lim i → ∞ kini {\ displaystyle R (C) = \ lim _ {i \ to \ infty} {k_ {i} \ over n_ {i}}}$ $R (C) = \ lim _ {я \ к \ infty} {k_ {я } \ over n_ {i}}$

Относительное расстояние семейства кодов C определяется как $δ (C) = lim i → ∞ dini {\ displaystyle \ delta (C) = \ lim _ {i \ to \ infty} {d_ {i} \ over n_ {i}}}$ $\ delta (C) = \ lim _ {i \ to \ infty} {d_ {i} \ over n_ {i}}$

Чтобы изучить отношенияh ip между $R (C) {\ displaystyle R (C)}$ $R (C)$ и $δ (C) {\ displaystyle \ delta (C)}$ $\ delta (C)$ , набор известны нижняя и верхняя границы блочных кодов.

Граница Хэмминга

R ≤ 1 - 1 n ⋅ log q ⋅ [∑ i = 0 ⌊ δ ⋅ n - 1 2 ⌋ (ni) (q - 1) i] {\ displaystyle R \ leq 1- {1 \ over n} \ cdot \ log _ {q} \ cdot \ left [\ sum _ {i = 0} ^ {\ left \ lfloor {{\ delta \ cdot n-1} \ over 2} \ right \ rfloor} {\ binom {n} {i}} (q-1) ^ {i} \ right]}

{\ displaystyle R \ leq 1- {1 \ over n} \ cdot \ log _ {q} \ cdot \ left [\ sum _ {i = 0} ^ {\ left \ lfloor {{\ delta \ cdot n-1} \ over 2} \ right \ rfloor} {\ binom {n } {i}} (q-1) ^ {i} \ right]}

Граница синглтона

Граница синглтона - это сумма скорости и относительное расстояние блочного кода не может быть намного больше 1:

R + δ ≤ 1 + 1 n {\ displaystyle R + \ delta \ leq 1 + {\ frac {1} {n}}}

R + \ delta \ leq 1 + {\ frac {1} {n}}

В другом слов, каждый блочный код удовлетворяет неравенству $k + d ≤ n + 1 {\ displaystyle k + d \ leq n + 1}$ $к + d \ leq n + 1$ . коды Рида – Соломона являются нетривиальными примерами кодов, которые удовлетворяют singleton, связанный с равенством.

Граница Плоткина

Для $q = 2 {\ displaystyle q = 2}$ $q = 2$ , $R + 2 δ ≤ 1 {\ displaystyle R + 2 \ delta \ leq 1}$ $R + 2 \ delta \ leq 1$ . Другими словами, $k + 2 d ≤ n {\ displaystyle k + 2d \ leq n}$ ${\ Displaystyle к + 2d \ Leq n}$ .

Для общего случая следующие границы Плоткина верны для любого $C ⊆ F qn {\ displaystyle C \ Subteq \ mathbb {F} _ {q} ^ {n}}$ $C \ substeq \ mathbb {F} _ {q} ^ {n}$ с расстоянием d:

Если $d = (1 - 1 q) n, | C | ≤ 2 q N {\ displaystyle d = \ left (1- {1 \ over q} \ right) n, | C | \ leq 2qn}$ ${\ displaystyle d = \ left ( 1- {1 \ over q} \ right) n, | C | \ leq 2qn}$
Если $d>(1 - 1 q) n, | C | ≤ qdqd - (q - 1) n {\ displaystyle d>\ left (1- {1 \ over q} \ right) n, | C | \ leq {qd \ over {qd- \ left (q-1 \ right) n}}}$ $d>\ left (1- {1 \ over q} \ right) n, | C | \ leq {qd \ over {qd- \ left (q-1 \ right) n} }$

Для любого q- код с расстоянием $δ {\ displaystyle \ delta}$ $\ delta$ , $R ≤ 1 - (qq - 1) δ + o (1) {\ displaystyle R \ leq 1- \ left ({q \ over {q- 1}} \ right) \ delta + o \ left (1 \ right)}$ ${\ displaystyle R \ Leq 1- \ влево ({д \ над {q-1}} \ вправо) \ дельта + о \ влево (1 \ вправо)}$

Граница Гилберта – Варшамова

$R ≥ 1 - H q (δ) - ϵ {\ displaystyle R \ geq 1-H_ {q } \ left (\ delta \ right) - \ epsilon}$ ${\ displaystyle R \ geq 1-H_ {q} \ left (\ delta \ right) - \ epsilon}$ , где $0 ≤ δ ≤ 1 - 1 q, 0 ≤ ϵ ≤ 1 - H q (δ) {\ displaystyle 0 \ leq \ delta \ leq 1- {1 \ over q}, 0 \ leq \ epsilon \ leq 1-H_ {q} \ left (\ delta \ right)}$ ${\ Displaystyle 0 \ Leq \ delta \ Leq 1- {1 \ над q}, 0 \ leq \ epsilon \ leq 1-H_ {q} \ left (\ delta \ right)}$ , $H q (x) = def - x ⋅ log q ⁡ xq - 1 - (1 - x) ⋅ журнал q ⁡ (1 - x) {\ displaystyle H_ {q} \ left (x \ right) ~ {\ overset {\ underset {\ mathrm {def}} {}} {=}} ~ -x \ cdot \ log _ {q} {x \ over {q-1}} - \ left (1-x \ right) \ cdot \ log _ {q} {\ left (1-x \ right)}}$ ${\ displaystyle H_ {q} \ left (x \ right) ~ {\ overset {\ underset {\ mathrm {def} } {}} {=}} ~ -x \ cdot \ log _ {q} {x \ over {q-1}} - \ left (1-x \ right) \ cdot \ log _ {q} {\ left (1-х \ справа)}}$ - q-ичная функция энтропии.

Граница Джонсона

Определить $J q (δ) = def (1 - 1 q) (1 - 1 - q δ q - 1) {\ displaystyle J_ {q} \ left (\ delta \ right) ~ {\ overset {\ underset {\ mathrm {def}} {}} {=}} ~ \ left (1- {1 \ over q} \ right) \ left (1 - {\ sqrt {1- {q \ delta \ over {q-1}}}} \ right)}$ ${\ displaystyle J_ {q} \ left (\ delta \ right) ~ {\ overset {\ underset {\ mathrm {def}} {}} {=} } ~ \ left (1- {1 \ over q} \ right) \ left (1 - {\ sqrt {1- {q \ delta \ over {q-1}}}} \ right)}$ .. Пусть $J q (n, d, e) {\ displaystyle J_ {q} \ left (n, d, e \ right)}$ ${\ displaystyle J_ {q} \ left ( n, d, e \ right)}$ - максимальное количество кодовых слов в шаре Хэмминга радиуса e для любого кода. $C ⊆ F qn {\ displaystyle C \ substeq \ mathbb {F} _ {q } ^ {n}}$ $C \ substeq \ mathbb {F} _ {q} ^ {n}$ расстояния d.

Тогда у нас есть граница Джонсона: $J q (n, d, e) ≤ qnd {\ displaystyle J_ {q} \ left (n, d, e \ right) \ leq qnd}$ ${\ displaystyle J_ {q} \ left (n, d, e \ right) \ leq qnd}$ , если $en ≤ q - 1 q (1 - 1 - qq - 1 ⋅ dn) = J q (dn) {\ displaystyle {e \ over n} \ leq {{q-1} \ over q} \ left ({1 - {\ sqrt {1- {q \ over {q-1}} \ cdot {d \ over n}}}} \, \ right) = J_ {q} \ left ( {d \ over n} \ right)}$ ${\ displaystyle {e \ over n} \ leq {{q-1} \ over q} \ left ({1 - {\ sqrt {1- {q \ over {q-1}}} \ cdot {d \ над n}}}} \, \ right) = J_ {q} \ left ({d \ over n} \ right)}$

Граница Элиаса – Бассалыго

R = log q ⁡ | C | n ≤ 1 - ЧАС Q (J ​​q (δ)) + о (1) {\ Displaystyle R = {\ log _ {q} {| C |} \ над n} \ Leq 1-H_ {q} \ left ( J_ {q} \ left (\ delta \ right) \ right) + o \ left (1 \ right)}

{\ displaystyle R = {\ log _ {q} { | C |} \ над n} \ leq 1-H_ {q} \ left (J_ {q} \ left (\ delta \ right) \ right) + o \ left (1 \ right)}

Упаковка сфер и решетки

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

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

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

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

См. Также

Ссылки

JH ван Линт (1992). Введение в теорию кодирования. GTM. 86(2-е изд.). Springer-Verlag. п. 31. ISBN 3-540-54894-7.
F.J. МакУильямс ; Нью-Джерси Слоан (1977). Теория кодов, исправляющих ошибки. Северная Голландия. п. 35. ISBN 0-444-85193-3.
W. Хаффман; В.Плесс (2003). Основы кодов исправления ошибок. Издательство Кембриджского университета. ISBN 978-0-521-78280-7.
С. Линь; Д. Дж. Младший Костелло (1983). Кодирование с контролем ошибок: основы и приложения. Прентис-Холл. ISBN 0-13-283796-X.

Внешние ссылки

Чаран Лэнгтон (2001) Концепции кодирования и блочное кодирование