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

10

Существует ли известная конструкция линейного кода с исправлением ошибок (с приемлемыми параметрами), такая, что при задании булева вектора v { 0 , 1 } n он также возвращает булев вектор WHP? (хотя это более F q )ECC:FqnFqmv{0,1}nFq

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

Если нет, то что если мы ослабим условие до Где E C C i возвращает i -ю координату E C C , ϵ сколь угодно мало и вероятность берется как для равномерного выбора v { 0 , 1 } n, так и для равномерного выбора координаты i [

Pr[ECCi(v){0,1}]>1ϵ
ECCiiECCϵv{0,1}n .i[m]

источник
3
Из любопытства, вы имеете в виду какие-либо приложения?
Цуёси Ито
Да, у меня действительно есть пара приложений для кода исправления ошибок с таким свойством. Тем не менее, я думаю, что это невозможно объяснить в рамках комментария. Вы можете связаться со мной по почте, если вы заинтересованы.
Спасибо за ответ. Если это не помещается в комментарии, у меня, вероятно, нет времени, чтобы все понять, так что я оставлю все как есть. Спасибо!
Tsuyoshi Ito

Ответы:

7

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

Махди Черагчи
источник
Означает ли это, что при заданном (линейном в F_q) коде Рида-Соломона вероятность того, что код вернет двоичное кодовое слово при заданном двоичном входе, равна 1? Не могли бы вы направить меня на какой-нибудь документ / опрос, в котором я могу прочитать об этой собственности более подробно? Я немного новичок в теории кодирования. Спасибо!
Лучшим справочным материалом для чтения двоичных кодов БЧХ являются классические учебники «Теория кодов, исправляющих ошибки» Мак-Вильямса и Слоана, а также «Введение в теорию кодирования» Ван Линта.
Махди Черагчи
1
@ TomGur: я не уверен, что коды BCH соответствуют вашим требованиям. В некоторой степени ответ зависит от того, сколько вычислительных усилий вы хотите, чтобы декодер приложил к задаче. «Готовые» декодеры являются декодерами с ограниченным расстоянием и корректируются только до уникального предела декодируемости (<половина минимального расстояния). Для кодов BCH значительная часть двоичного пространства выходит за пределы допустимого диапазона, что приведет к ошибке декодера. Просто иметь код недостаточно, если вы не укажете алгоритм декодирования (не у всех ECC есть эффективный известный).
Юрки Лахтонен