Код Justesen - Justesen code

Двоичные коды Justesen
Названный в честь	Йорн Юстесен
Классификация
Тип	Линейный блочный код
Длина блока
Длина сообщения
Ставка	=
Расстояние	куда для маленьких .
Размер алфавита	2
Обозначение	-код
Характеристики
	постоянная скорость, постоянное относительное расстояние, постоянный размер алфавита

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

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

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

Коды Justesen выводятся как конкатенация кода из Код Рида – Соломона и Ансамбль Wozencraft.

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

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

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

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

Определение

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

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

Затем мы применяем каждый код из N линейных внутренних кодов к каждой координате этого кодового слова, чтобы получить окончательное кодовое слово; то есть, ${displaystyle 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}))}$ .

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

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

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

Собственность кода Justesen

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

Теорема

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

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

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

{displaystyle m_ {1} eq m_ {2} слева (mathbb {F} _ {q ^ {k}} ight) ^ {K},}

мы хотим получить нижнюю оценку для ${displaystyle Delta (C ^ {*} (m_ {1}), C ^ {*} (m_ {2})).}$

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

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

{displaystyle {egin {align} C_ {out} (m_ {1}) & = left (c_ {1} ^ {1}, cdots, c_ {N} ^ {1} ight) C_ {out} (m_ { 2}) & = left (c_ {1} ^ {2}, cdots, c_ {N} ^ {2} ight) end {выровнено}}}

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

{displaystyle Delta left (C_ {in} ^ {i} left (c_ {i} ^ {1} ight), C_ {in} ^ {i} left (c_ {i} ^ {2} ight) ight) geqslant H_ {q} ^ {- 1} left ({frac {1} {2}} - varepsilon ight) cdot 2k.}

Далее, если мы имеем ${displaystyle T}$ числа ${displaystyle 1leqslant ileqslant N}$ такой, что ${displaystyle c_ {i} ^ {1} eq c_ {i} ^ {2}}$ и код ${displaystyle C_ {in} ^ {i}}$ имеет расстояние ${displaystyle geqslant H_ {q} ^ {- 1} ({frac {1} {2}} - varepsilon) cdot 2k,}$ тогда

{displaystyle Delta left (C ^ {*} (m_ {1}), C ^ {*} (m_ {2}) ight) geqslant H_ {q} ^ {- 1} left ({frac {1} {2}) } -varepsilon ight) cdot 2kcdot T.}

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

{displaystyle S = left {i: 1leqslant ileqslant N, c_ {i} ^ {1} eq c_ {i} ^ {2} ight}.}

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

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

Из-за Теорема Возенкрафта об ансамбле, есть не более ${displaystyle varepsilon N}$ линейные коды с расстоянием менее ${displaystyle H_ {q} ^ {- 1} ({frac {1} {2}} - varepsilon) cdot 2k,}$ так

{displaystyle Tgeqslant | S | -варепсилон Ngeqslant (1-R) ​​N-варепсилон N = (1-R-варепсилон) N.}

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

{displaystyle Delta (C ^ {*} (m_ {1}), C ^ {*} (m_ {2})) geqslant H_ {q} ^ {- 1} left ({frac {1} {2}} - varepsilon ight) cdot 2kcdot Tgeqslant H_ {q} ^ {- 1} left ({frac {1} {2}} - varepsilon ight) cdot 2kcdot (1-R-varepsilon) cdot N.}

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

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

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

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

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

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

Пример кода Justesen

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

Позволять р быть кодом Рида-Соломона длины N = 2^м − 1, классифицировать K и минимальный вес N − K + 1.

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

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

{displaystyle mathbf {b} = left (a_ {1}, a_ {1}, a_ {2}, alpha ^ {1} a_ {2}, ldots, a_ {N}, alpha ^ {N-1} a_ { Ночь)}

и разреши c вектор длины 2N м получен из б выражая каждый элемент F как двоичный вектор длины м. В Код Justesen - линейный код, содержащий все такие c.

Параметры этого кода - длина 2м N, измерение м K и минимальное расстояние по меньшей мере

{displaystyle sum _ {i = 1} ^ {ell} i {inom {2m} {i}},}

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

Код Justesen - Justesen code

Содержание

Определение

Собственность кода Justesen

Теорема

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

Комментарии

Пример кода Justesen

Смотрите также

Рекомендации