Логический код, исправляющий ошибки над

Существует ли известная конструкция линейного кода с исправлением ошибок (с приемлемыми параметрами), такая, что при задании булева вектора он также возвращает булев вектор WHP? (хотя это более ) $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ $v\in \{0,1\}^n$ $\mathbb{F}_q$

(то есть , где вероятность принимается равномерно, выбирая , а сколь угодно мал)) $\Pr[\mathsf{ECC}(v) \in \{0,1\}^m]>1-\epsilon$ $v\in \{0,1\}^n$ $\epsilon$

Если нет, то что если мы ослабим условие до Где возвращает -ю координату , сколь угодно мало и вероятность берется как для равномерного выбора и для равномерного выбора координаты

Pr [{E C C}_{i} (v) \in {0, 1}] > 1 - ϵ

$\Pr[\mathsf{ECC}_i(v) \in \{0,1\}]> 1-\epsilon$

{E C C}_{i}

$\mathsf{ECC}_i$

i

$i$

E C C

$\mathsf{ECC}$

ϵ

$\epsilon$

v \in {0, 1}^{n}

$v\in \{0,1\}^n$

i \in [m]

$i\in[m]$

Из любопытства, вы имеете в виду какие-либо приложения?

Цуёси Ито

Да, у меня действительно есть пара приложений для кода исправления ошибок с таким свойством. Тем не менее, я думаю, что это невозможно объяснить в рамках комментария. Вы можете связаться со мной по почте, если вы заинтересованы.

Спасибо за ответ. Если это не помещается в комментарии, у меня, вероятно, нет времени, чтобы все понять, так что я оставлю все как есть. Спасибо!

Tsuyoshi Ito

Ответы:

Да. Например, код Рида-Соломона содержит код BCH, который является двоичным линейным кодом, в качестве субкода. Они называются подполями-подкодами.

Махди Черагчи
источник

Означает ли это, что при заданном (линейном в F_q) коде Рида-Соломона вероятность того, что код вернет двоичное кодовое слово при заданном двоичном входе, равна 1? Не могли бы вы направить меня на какой-нибудь документ / опрос, в котором я могу прочитать об этой собственности более подробно? Я немного новичок в теории кодирования. Спасибо!

Лучшим справочным материалом для чтения двоичных кодов БЧХ являются классические учебники «Теория кодов, исправляющих ошибки» Мак-Вильямса и Слоана, а также «Введение в теорию кодирования» Ван Линта.

Махди Черагчи

@ TomGur: я не уверен, что коды BCH соответствуют вашим требованиям. В некоторой степени ответ зависит от того, сколько вычислительных усилий вы хотите, чтобы декодер приложил к задаче. «Готовые» декодеры являются декодерами с ограниченным расстоянием и корректируются только до уникального предела декодируемости (<половина минимального расстояния). Для кодов BCH значительная часть двоичного пространства выходит за пределы допустимого диапазона, что приведет к ошибке декодера. Просто иметь код недостаточно, если вы не укажете алгоритм декодирования (не у всех ECC есть эффективный известный).

Юрки Лахтонен