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

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

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

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

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

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

Код блока и его параметры [ править ]

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

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

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

Длина сообщения k [ править ]

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

Длина блока n [ править ]

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

Ставка R [ править ]

Скорость блочного кода определяются как отношение между его длиной сообщения и его длиной блока:

${\ Displaystyle R = к / п}$.

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

Расстояние d [ править ]

Расстояние или минимальное расстояние 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_{1})+C(m_{2})]=\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}}}$

Для любого д -ичного кода с расстоянием ,${\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 }$, Где , является д - позиционной функция энтропии.${\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]
• Упаковка сфер

Ссылки [ править ]

• Дж. Х. ван Линт (1992). Введение в теорию кодирования . GTM . 86 (2-е изд.). Springer-Verlag. п. 31 . ISBN 3-540-54894-7. CS1 maint: discouraged parameter (link)
• FJ MacWilliams ; NJA Sloane (1977). Теория кодов, исправляющих ошибки . Северная Голландия. п. 35 . ISBN 0-444-85193-3. CS1 maint: discouraged parameter (link)
• В. Хаффман; В.Плесс (2003). Основы кодов исправления ошибок . Издательство Кембриджского университета. ISBN 978-0-521-78280-7. CS1 maint: discouraged parameter (link)
• С. Линь; DJ мл. Костелло (1983). Кодирование с контролем ошибок: основы и приложения . Прентис-Холл. ISBN 0-13-283796-X.

Внешние ссылки [ править ]

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