16.2. КОМПОЗИЦИОННЫЕ КОДЫ




Композиционные коды (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






Index Prev Next