посоветуйте код с восстановлением ошибок

код хэмминга, например

А какой длины выйдет одно сообщение, чтобы была возможность восстановить 2(1) символа?

В рефератах и на википедии в связи с поскриптумом ничего не понимаю к сожалению

хемминга не пойдет, он во-первых бинарный, во вторых исправляет только одиночные ошибки. если нужна минимальная избыточность, то смотри в сторону БЧХ, в частности Рида-Соломона

$allow = array('пиво','хлеб');
$scan = 'хлев';
$l = 100500;

if(!in_array($scan, $allow)) {
    $found = '';
    foreach($allow as $word) {
        $lev = levenshtein($scan,$word);
        if( $lev < $l) {
            $found = $word;
            $l = $lev;
        }
    }
}

if($found != '' && $l <= 2) echo 'Таки '.$found;
else echo 'Тьху ты ';

юмор конечно, но все-же :)

Пытаюсь разобраться с Ридом-Соломоном по http://www.insidepro.com/kk/027/027r.shtml#_ftnref1 вот этой статье. что-то застрял на:

кодирование производится с использованием сдвигового feedback-регистра, * заполненного соответствующими элементами массива g[] с порожденным * полиномом внутри, процедура генерации которого уже обсуждалась в * предыдущей главе.

Как этот массив сгенерировать не понимаю в упор. И еще не совсем понятно в каком виде должны быть входные данные, пишут что в полиномальном, но как перевести число 105, например, в него?

//Причем что самое смешное сижу уже 2 часа разбираюсь, а нужно это даже совсем не мне, а коллеге, которому я решил помочь по доброте :) Он уже домой ушел, а я до сих пор по его проблеме разбираюсь

Если объём некритичен, сделай информацию в трёх экземплярах.

PS: Институтский курс теории информации забыл уже начисто.

Странно, а задание сформулированно почти как лабораторка.
Могу посоветовать код Рида-Соломона. При добавлении t контрольных символов он распознаёт t любых ошибок и исправляет floor(t/2), насколько я помню.

Если объём некритичен, сделай информацию в трёх экземплярах.

Ну не то что критичен, но человеку писать ручкой. Примерно 20 раз за день. Да и чем больше цифр тем больше вероятность ошибки. Как я определю какой набор цифр верен если будет в 1-й тройке одна ошибка и во 2-й тройке одна ошибка? Тут правильно насчет Рида-Соломона соломона подсказали(можно с сигналом в 3 знака + 4 контрольных исправлять гарантированно 2 ошибки), но что-то я не осиливаю.

Могу посоветовать код Рида-Соломона. При добавлении t контрольных символов он распознаёт t любых ошибок и исправляет floor(t/2), насколько я помню.

Да, именно так. Но вот написать кодер\декодер пока что не осилил. Причем кодер нужен одноразовый 1-200 зашифровать и использовать, а после сканирования только дешифровывать.

Покупка принтера решает эту задачу позволяя использовать баркоды.

2.5 тыс. принтеров покупать и людям по городу с принтерами бегать? Это вообще для заполнения отчетности работниками(мерчандайзеры) делается.

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

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

В данной ситуации это не подходит по нескольким причинам.

1. финансовые(наклейки денег стоят)

2. если чувак неправильно цифру напишет - это можно будет распознать, а если он не ту наклейку наклеит в запаре, то хреново для отчетности.

3. Ну и ТЗ такое что чуваки по России с ручками и бумажками бегают, а я вообще к этому проекту боком, коллеге помочь решил. Т.е. я не решаю с баркодами или с цифрами все это делать.

3. Ну и ТЗ такое что чуваки по России с ручками и бумажками бегают

а потом жить стало проще - появились перфокарты :)

а потом жить стало проще - появились перфокарты :)

Ну вообще конечно все не так. Чуваки ходят с КПК, но если КПК ломается или еще что, то как запасной вариант - бумага.

Задача стоит в том что из двух цифр записанных на бумажке одна может принять случайное значение? Ну тогда уж дейтсвительно три раза написать.

если исправления ошибки не нужно то заложи просто контрольную сумму.

Можно даже всё равно обойтись двумя символами, только шестнадцатиричными. Лишние биты использовать для контрольной суммы.

там на пальцах не объяснишь, если ты ничего не помнишь. нужно как минимум полиномиальную арифметику и поля Галуа хорошо представлять. полистай Блейхута, «Теория и практика кодов, контролирующих ошибки», освежи в памяти

Как я определю какой набор цифр верен если будет в 1-й тройке одна ошибка и во 2-й тройке одна ошибка?

Голосованием, те кто в меньшинстве не правы. Это алгоритм для ленивых, если думать лень а результат нужен быстро.

Тут правильно насчет Рида-Соломона соломона подсказали

Готовая реализация в интернете уже должна где-то быть.

Готовая реализация в интернете уже должна где-то быть.

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