Блокировать код

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

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

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

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

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

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

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

Формально блочный код представляет собой инъективное отображение

${\displaystyle C:\Sigma ^{k}\to \Sigma ^{n}}$.

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

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

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

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

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

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

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

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

${\displaystyle d:=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]}$.

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

${\displaystyle \min _{m_{1},m_{2}\in \Sigma ^{k} \atop 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_{2})-C(m_{1})]=\min _{m\in \Sigma ^{k} \atop m\neq \mathbf {0} }w[C(m)]=w_{\min }}$.

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

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

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

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

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

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

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

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

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

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

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

${\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:

${\displaystyle R+\delta \leq 1+{\frac {1}{n}}}$.

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

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

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

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

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

${\displaystyle R\geq 1-H_{q}\left(\delta \right)-\epsilon }$, где , — q -ичная функция энтропии.${\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta \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-x\right)}}$

Определим . Пусть будет максимальным числом кодовых слов в шаре Хэмминга радиуса e для любого кода с расстоянием d .${\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(n,d,e\right)}$${\displaystyle C\subseteq \mathbb {F} _{q}^{n}}$

Тогда у нас есть граница Джонсона  : , если${\displaystyle J_{q}\left(n,d,e\right)\leq qnd}$${\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 R={\log _{q}{|C|} \over n}\leq 1-H_{q}\left(J_{q}\left(\delta \right)\right)+o\left(1\right)}$

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

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

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

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

• Пропускная способность канала
• Теорема Шеннона–Хартли
• Шумный канал
• Расшифровка списка ^[1]
• Упаковка сфер

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