Код Юстесена

Двоичные коды Юстесена
Назван в честь	Йорн Юстесен
Классификация
Тип	Линейный блочный код
Длина блока	$n$
Длина сообщения	$k$
Ставка	= ${\frac {R}{2}}={\frac {k}{2n}}$
Расстояние	$\delta n$ где $\delta \geq {\Big (}1-R-\epsilon {\Big )}H_{2}^{-1}{\big (}{\frac {1}{2}}-\epsilon {\big )}\sim 0.11(1-R-\epsilon )$ для маленьких $\epsilon >0$.
Размер алфавита	2
Обозначения	$\left[n,k/2,\delta n\right]_{2}$-код
Характеристики
постоянная скорость, постоянное относительное расстояние, постоянный размер алфавита

В теории кодирования коды Юстесена образуют класс кодов с исправлением ошибок , которые имеют постоянную скорость, постоянное относительное расстояние и постоянный размер алфавита.

До того, как был обнаружен код исправления ошибок Юстесена, не было известно ни одного кода исправления ошибок, который имел бы все эти три параметра в качестве констант.

Впоследствии были обнаружены и другие коды ECC с этим свойством, например коды-расширители .Эти коды имеют важные приложения в информатике , например, при построении выборочных пространств с малым смещением .

Коды Юстесена получаются как конкатенация кода Рида -Соломона и ансамбля Возенкрафта .

Используемые коды Рида-Соломона обеспечивают постоянную скорость и постоянное относительное расстояние за счет размера алфавита, линейного по длине сообщения.

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

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

Это отличается от обычной конкатенации кода, где внутренние коды одинаковы для каждой позиции. Код Юстесена можно построить очень эффективно, используя только логарифмическое пространство .

Определение

Код Юстесена представляет собой объединение $(N,K,D)_{q^{k}}$ внешний код $C_{out}$ и разные $(n,k,d)_{q}$ внутренние коды $C_{in}^{i}$, для $1\leq i\leq N$.

Точнее, конкатенация этих кодов, обозначаемая $C_{out}\circ (C_{in}^{1},...,C_{in}^{N})$, определяется следующим образом. Учитывая сообщение $m\in [q^{k}]^{K}$, мы вычисляем кодовое слово, созданное внешним кодом $C_{out}$: $C_{out}(m)=(c_{1},c_{2},..,c_{N})$.

Затем мы применяем каждый код из N линейных внутренних кодов к каждой координате этого кодового слова, чтобы получить окончательное кодовое слово; то есть, $C_{out}\circ (C_{in}^{1},..,C_{in}^{N})(m)=(C_{in}^{1}(c_{1}),C_{in}^{2}(c_{2}),..,C_{in}^{N}(c_{N}))$.

Вернитесь к определению внешнего кода и линейных внутренних кодов. Это определение кода Юстесена имеет смысл, поскольку кодовое слово внешнего кода представляет собой вектор с $N$ элементы, и мы имеем $N$ линейные внутренние коды, применимые к тем $N$ элементы.

Здесь для кода Юстесена внешний код $C_{out}$ выбирается код Рида-Соломона над полем $\mathbb {F} _{q^{k}}$ оценивается более чем $\mathbb {F} _{q^{k}}-\{0\}$ скорости ​ $R$, $0$ < $R$ < $1$.

Внешний код $C_{out}$ иметь относительное расстояние $\delta _{out}=1-R$ и длина блока $N=q^{k}-1$. Совокупность внутренних кодов – ансамбль Wozencraft. $\{C_{in}^{\alpha }\}_{\alpha \in \mathbb {F} _{q^{k}}^{*}}$.

Свойство кода Юстесена

Поскольку линейные коды в ансамбле Вонзенкрафта имеют скорость ${\frac {1}{2}}$, код Юстесена представляет собой составной код $C^{*}=C_{out}\circ (C_{in}^{1},C_{in}^{2},..,C_{in}^{N})$ со ставкой ${\frac {R}{2}}$. У нас есть следующая теорема, которая оценивает расстояние составного кода $C^{*}$.

Теорема

Позволять $\varepsilon >0.$ Затем $C^{*}$ имеет относительное расстояние не менее $(1-R-\varepsilon )H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right).$

Доказательство

Чтобы доказать нижнюю оценку расстояния кода $C^{*}$ мы доказываем, что расстояние Хэмминга произвольной, но отличной пары кодовых слов имеет нижнюю границу. Так что пусть $\Delta (c^{1},c^{2})$ быть расстоянием Хэмминга двух кодовых слов $c^{1}$ и $c^{2}$. Для любого данного

$m_{1}\neq m_{2}\in \left(\mathbb {F} _{q^{k}}\right)^{K},$

нам нужна нижняя граница для $\Delta (C^{*}(m_{1}),C^{*}(m_{2})).$

Обратите внимание, что если $C_{out}(m)=(c_{1},\cdots ,c_{N})$, затем $C^{*}(m)=(C_{in}^{1}(c_{1}),\cdots ,C_{in}^{N}(c_{N}))$. Итак, для нижней границы $\Delta (C^{*}(m_{1}),C^{*}(m_{2}))$, нам нужно принять во внимание расстояние $C_{in}^{1},\cdots ,C_{in}^{N}.$

Предполагать

${\begin{aligned}C_{out}(m_{1})&=\left(c_{1}^{1},\cdots ,c_{N}^{1}\right)\\C_{out}(m_{2})&=\left(c_{1}^{2},\cdots ,c_{N}^{2}\right)\end{aligned}}$

Напомним, что $\left\{C_{in}^{1},\cdots ,C_{in}^{N}\right\}$ это ансамбль Wozencraft . Согласно «теореме ансамбля Вонзенкрафта», существует как минимум $(1-\varepsilon )N$ линейные коды $C_{in}^{i}$ у которых есть расстояние $H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$ Так что если для некоторых $1\leqslant i\leqslant N,c_{i}^{1}\neq c_{i}^{2}$ и код $C_{in}^{i}$ имеет расстояние $\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k,$ затем

$\Delta \left(C_{in}^{i}\left(c_{i}^{1}\right),C_{in}^{i}\left(c_{i}^{2}\right)\right)\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$

Далее, если мы имеем $T$ цифры $1\leqslant i\leqslant N$ такой, что $c_{i}^{1}\neq c_{i}^{2}$ и код $C_{in}^{i}$ имеет расстояние $\geqslant H_{q}^{-1}({\tfrac {1}{2}}-\varepsilon )\cdot 2k,$ затем

$\Delta \left(C^{*}(m_{1}),C^{*}(m_{2})\right)\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\cdot T.$

Итак, теперь последняя задача — найти нижнюю границу для $T$. Определять:

$S=\left\{i\ :\ 1\leqslant i\leqslant N,c_{i}^{1}\neq c_{i}^{2}\right\}.$

Затем $T$ количество линейных кодов $C_{in}^{i},i\in S$ имея расстояние $H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$

Теперь мы хотим оценить $|S|.$ Очевидно $|S|=\Delta (C_{out}(m_{1}),C_{out}(m_{2}))\geqslant (1-R)N$.

Согласно теореме об ансамбле Возенкрафта , существует не более $\varepsilon N$ линейные коды, имеющие расстояние меньше $H_{q}^{-1}({\tfrac {1}{2}}-\varepsilon )\cdot 2k,$ так

$T\geqslant |S|-\varepsilon N\geqslant (1-R)N-\varepsilon N=(1-R-\varepsilon )N.$

Наконец, у нас есть

$\Delta (C^{*}(m_{1}),C^{*}(m_{2}))\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\cdot T\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\cdot (1-R-\varepsilon )\cdot N.$

Это справедливо для любого произвольного $m_{1}\neq m_{2}$. Так $C^{*}$ имеет относительное расстояние не менее $(1-R-\varepsilon )H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right),$ что завершает доказательство.

Комментарии

Мы хотим рассмотреть «строго явный код». Итак, вопрос в том, что такое «строго явный код». Грубо говоря, для линейного кода свойство «явность» связано со сложностью построения его порождающей матрицы G.

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

Для других кодов, которые не являются линейными, мы можем учитывать сложность алгоритма кодирования.

Итак, мы видим, что ансамбль Вонзенкрафта и коды Рида-Соломона строго явны. Таким образом, мы имеем следующий результат:

Следствие: составной код $C^{*}$ является асимптотически хорошим кодом (т. е. скорость $R$ > 0 и относительное расстояние $\delta$ > 0 при малых q) и имеет сильно явную конструкцию.

Пример кода Юстесена

Следующий немного отличающийся код называется кодом Юстесена в MacWilliams/MacWilliams. Это частный случай рассмотренного выше Код Юстесена для очень специфического ансамбля Wonzencraft:

Пусть R — код Рида-Соломона длины N = 2. ^м − 1, ранг K и минимальный вес N − K + 1.

Символы R являются элементами F = GF(2 ^м ), а кодовые слова получаются путем взятия каждого многочлена ƒ над F степени меньше K и перечисления значений ƒ на ненулевых элементах F в некотором заранее определенном порядке.

Пусть α — элемент F примитивный . Для кодового слова a = ( a ₁ , ..., a _N ) из R пусть b будет вектором длины 2 N над F, заданным формулой

$\mathbf {b} =\left(a_{1},a_{1},a_{2},\alpha ^{1}a_{2},\ldots ,a_{N},\alpha ^{N-1}a_{N}\right)$

и пусть c будет вектором длины 2 N m, полученным из b путем выражения каждого элемента F как двоичного вектора длины m . Код Юстесена — это линейный код, содержащий все такие c .

Параметрами этого кода являются длина 2 м N , размер м K и минимальное расстояние не менее

$\sum _{i=1}^{\ell }i{\binom {2m}{i}},$

где $\ell$ является наибольшим целым числом, удовлетворяющим $\sum _{i=1}^{\ell }{\binom {2m}{i}}\leq N-K+1$. (Доказательство см. в MacWilliams/MacWilliams.)

См. также

• Составной код исправления ошибок
• Линейный код
• Исправление ошибок Рида-Соломона
• Возенкрафт вместе

Ссылки

• Лекция 28: Кодекс Юстесена. Курс теории кодирования. Профессор Атри Рудра .
• Лекция 6: Сцепленные коды. Коды Форни. Коды Юстесена. Основная теория кодирования .
• Дж. Юстесен (1972). «Класс конструктивных асимптотически хороших алгебраических кодов». IEEE Транс. Инф. Теория . 18 (5): 652–656. дои : 10.1109/TIT.1972.1054893 .
• Ф. Дж. МакВильямс ; НЯА Слоан (1977). Теория кодов, исправляющих ошибки . Северная Голландия. стр. 306–316 . ISBN  0-444-85193-3 .