Какой алгоритм коррекции ошибок выбрать для двумерного баркода?
Есть простой двумерный баркод 5х5 клеток, 16 бит под данные и 9 соответственно остаются.
Вопрос: возможно ли в оставшиеся 9 бит вместить данные для кооррекции ошибок, или только контрольную сумму и какой алгоритм посоветуете?
Update:
Мне нужно определить ориентацию кода, если пытаться это сделать, последовательно для четырех положений, ожидая, что код коррекции сойдется только для правильного. Или же отдать 4 бита под ориентацию (просто зафиксировав их), а остальные 5 под контрольную сумму? Мне важнее исключить неверные распознования, чем корректировать ошибки.
Мне кажется, или обычный контроль четности по строкам и столбцам (4 контрольных бита в последнем столбце + 4 контрольных бита в последней строке) позволит Вам исправлять любую одиночную ошибку ? (она будет находиться на пересечении строки и столбца с поврежденными четностями; а повреждение в контрольных разрядах будет определяться отсутствием нарушений в другом измерении).
Ну и из 9-ого бита, наверное, можно что-то полезное извлечь ...
Увы, мне кажется - нет. Одиночное искажение контрольных разрядов определяется так, как я описал выше, а на двойное - этот код все равно не рассчитан. Так что в 9-ый бит можно что-нибудь другое скрывать ;-)
Андрей: Согласен. В вашем варианте ситуация "строка испортилась, а столбцы - нет" означает, что испортился контрольный бит в строке - значит, последний бит действительно ни к чему. Разве что, попробовать с его помощью детектировать двойные ошибки?
Да, это первое что пришло в голову - детектировать двойные ошибки было бы заманчиво и полезно. Однако, признаюсь, я не смог придумать алгоритма. Похоже, для детектирования двойных требуется еще как минимум 4-5 бит.
Хотя возможно, если в 9-ый бит сохранять четность всех остальных 24-х, то сохранение его четности при наличии иных искажений в контрольных разрядах и будет фактом наличия двойной ошибки.
Да, записываем в 25-й бит сумму 16 рабочих битов (или контрольную сумму сумм по строкам - что то же самое). Получаем табличку, в которой сумма в каждой строке и каждом столбце нулевая. Если произойдёт одна ошибка - то нарушатся одна строка и один столбец (и мы сможем её исправить), если две - то нарушатся две строки и/или два столбца.
Двойную ошибку тоже можно исправить: если она произошла в одном столбце или строке. Вы можете оценить вероятность двойной ошибки, когда биты коррекции не помогут?
Виктор: Если двойная ошибка произошла в двух битах одного столбца, то вы узнаете, в каких строках она была, но не узнаете, в каком столбце: ведь в нём контрольная сумма в порядке.
Для коррекции двойной ошибки в блоке из 25 бит необходимо чтобы контрольные разряды могли нести log2(1+25+25*24) бит информации (граница Хемминга), а это получается 9,29 бит, так что исправлять двойные ошибки в блоке из 25 бит код с 9 контрольными битами не сможет никак. Максимум: исправлять одиночную + выявлять факт двойной.
Для правильного вопроса надо знать половину ответа
Стандартный код Хэмминга, в Вашем случае вариант (31, 26) - 26 бит данных, 5 бит контроля. Восстанавливает одиночные ошибки и обнаруживает двойные ошибки.
