Композиционные коды (product code) строятся так: из информационных битов строится двумерная решетка и к ней добавляются проверочные биты как к столбцам так и к строкам +------------+-+ |DDDDDDDDDDDD|P| |DDDDDDDDDDDD|P| |DDDDDDDDDDDD|P| D - данные |DDDDDDDDDDDD|P| P - четность +------------+-+ |PPPPPPPPPPPP|P| +------------+-+ строки код Crow с расстоянием Drow столбцы код Ccol с дистанцией Dcol Минимальная дистанция = Drow * Dcol (поэтому код называется product code - код произведение) Если один символ проверки на четность в каждом столбце/строке то дистанция = Drow * Dcol = 2 * 2 = 4 Т.е. код гарантированно обнаруживает 1,2 или 3 ошибки. Или обнаруживает 1,2 ошибки и исправляет одну. 4 ошибки по углам уже не обнаруживаются: +------------+-+ | | | | X X | | | | | | X X | | | | | +------------+-+ | | | +------------+-+ В качестве примера будем использовать блок 3x3 (a1..a9): ----------------- a1 a2 a3 | b1 a4 a5 a6 | b2 a7 a8 a9 | b3 ------------+--- b4 b5 b6 | b7 ---------------- b1 = a1 (+) a2 (+) a3 b2 = a4 (+) a5 (+) a6 b3 = a7 (+) a8 (+) a9 b4 = a1 (+) a4 (+) a7 b5 = a2 (+) a5 (+) a8 b6 = a3 (+) a6 (+) a9 b7 = XOR(a1,..a9,b1..b6) При длинне данных X**2, длинна проверок простого композиционного кода (2X+1) X DATA CODE CODE % 3 9 7 78% 10 100 21 21% 100 10000 201 2%
# - место ошибки * - место нарушения четности ----------------- a1 a2 a3 | b1 a4 a5 a6 | b2 ОШИБКА В ДАННЫХ a7 a8# a9 | b3* <-- здесь A8 ------------+--- b4 b5* b6 | b7* ошибка ---------------- ^ | здесь Строка + Столбец + Ошибка => ошибка в данных Одиночные ошибки
----------------- a1 a2 a3 | b1 a4 a5 a6 | b2 ОШИБКА В КОДЕ a7 a8 a9 | b3 B4 ------------+--- b4# b5 b6 | b7* ошибка ---------------- ^ | здесь Столбец + Ошибка => ошибка в коде столбца
----------------- a1 a2 a3 | b1 ОШИБКА В КОДЕ a4 a5 a6 | b2 B7 a7 a8 a9 | b3 ------------+--- b4 b5 b6 | b7# ошибка ---------------- Ошибка => ошибка в b7
В одном столбце/строке: ----------------- a1 a2 a3 | b1 a4# a5 a6 | b2* <- здесь a7# a8 a9 | b3* <- здесь ------------+--- b4 b5 b6 | b7 ---------------- Двойная ошибка обнаружена, но исправить ее не можем, т.к. не знаем столбец. Двойные ошибки
В разных строках: ----------------- a1# a2 a3 | b1* <--- a4 a5# a6 | b2* <--- a7 a8 a9 | b3 ------------+--- b4* b5* b6 | b7 ---------------- ^ ^ | | Двойная ошибка обнаружена, можем ее исправить.
----------------- a1 a2 a3 | b1 a4 a5 a6 | b2# <--- a7 a8 a9 | b3 ------------+--- b4# b5 b6 | b7 ---------------- ^ | b7 ошибки не имеет => двойная ошибка.
----------------- a1 a2 a3# | b1* a4 a5 a6 | b2 a7 a8 a9 | b3 ------------+--- b4 b5 b6* | b7# -> b7 виден как нет ошибки => двойная ошибка. ----------------
Композиционные коды могут строится и на основе строчных/столбцовых кодов с другими длиннами дистанции. Тогда они смогут исправлять/детектировать большее число ошибок. +------------+---+ | | | | | | | | | | | | +------------+---+ | | | | | | +------------+---+
Двумерные композиционные коды - это не предел. Можно строить product коды и с большей размерностью.
HoVer code