Коды в гранично-ранговой метрике

В некоторых приложениях возникает следующая проблема, ошибок: Информационные символы должны храниться в ( М х N) массивах. Некоторые из этих символов по ошибке записаны таким образом, что все искаженные символы находятся в одном или нескольких строках или столбцах (или обоих). Мы называем такие ошибки как ошибки решетчатой конфигурации. На рис. 1 показана, схема, ошибки решетчатой конфигурации, все искаженные символы сосредоточены в трёх столбцах и двух строках. Эти ошибки решетчатой конфигурации могут быть найдены в массивах микросхем памяти [1-3] или в записи магнитной ленты [4-6].

В системе параллельных каналов связи с помехами можно рассматривать каждое сообщение как двоичную матрицу с размером М х N, где число каналов равно М, длительность передачи по каждому из каналов равна N. Систему можно детализировать более подробно, как показано на. рис. 2. Для передачи данных во всех каналах используются двоичные сигналы. В процессе передачи сообщений возникают различные специфические ошибки. Ошибки возникают в столбцах матрицы сообщения, когда, в некоторые моменты времени встречаются импульсные помехи. Когда, в одном или нескольких каналах появляются медленные замирания сигналов и узкополосные помехи, то ошибки возникают в строках [7].

«Московский физико-технический институт (национальный исследовательский университет)», 2019

Рис. 2. Система, параллельных каналов связи с помехами

Э.М. Габидулиным [7], [8] были введены граничные коды, исправляющие ошибки решетчатой конфигурации. Коды могут исправить ошибочные строки и столбцы.

Пусть у = г + е, где г - кодовая матрица, у - полученная матрица, е - матрица ошибки. Пусть граничный ранг р(е) = 2, и предположим, что матрица е

0		1	0
	0	0	0
е =	1	1	0
	0	1	0
0		0	0

0 0

0 0

0 1

0 0

Легко заметить, что искаженные символы сосредоточены в третьей строке и втором столбце.

В разделе 2 написаны некоторые, в основном известные, важные определения и кодовое расстояние в гранично-ранговой метрике. В разделе 3 описывается конструкция граничноранговых кодов, которые были введены Э.М. Габидулиным [7] в 1985 году. В разделе 4 рассматриваются коды, исправляющие одиночные решетчатые ошибки. Для этого случая приведём пример кода (4, 2, 3), исправляющего ошибочный столбец в разделе 5.

2.    Гранично-ранговое расстояние

Граничный ранг р(Д) двоичной матрицы определяется как минимальное число линий (строк и столбцов), в которых содержатся все ненулевые элементы матрицы [7], [10].

Максимальный граничный ранг равен, очевидно,

D = max |А| = min(m, п).

А

Расстоянием между матрицами Аі и А2 называется граничный ранг их разности:

d(A i , А 2 ) = р(А 1 — А 2 ).

Произвольное множество (т х п)-матриц С = С(т, п) = Ai , A2 ,..., Ам называется кодом мощности М. Кодовое расстояние равно, по определению, минимальному из попарных расстояний между элементами кода:

d = min р(А г — Aj).                                    (1)

г=3

Гранично-ранговое расстояние имеет все свойства обычного расстояния [9]:

• 1)    d(A, В) = 0 о А = В-

• 2)    d(A, С ) + d(C, В ) >  d(A, В) - неравенство треугольника;

• 3)    d(B,A) = d(A, В) - свойство симметричности.

Первое и третье свойства получены из отмеченного выше соотношения

d(A, В) = p(A — В) = р(В — A).

Аналогично

d(A,C ) + d(C, В) =

= p(A — С ) + р(С — В) >  p((A — С ) + (С — В )) = = p(A — В ) = d(A — В).

Таким образом, второе свойство расстояния доказано.

Скорость кода определяется отношением

R =

log2^ тп

Если кодовое расстояние d(C ) = d, то существует способ декодирования этого кода, исправляющего все решетчатые конфигурации ошибок, в которых граничный ранг не превышает величину t = [(d — 1)/2].

Если код С имеет гранично-ранговое расстояние d, то для скорости кода выполняется неравенство

R < 1 —

d

—

D

Код, имеющий длину п, к информационных символов и минимальное граничноранговое расстояние d, называется линейным гранично-ранговым кодом (n,k,d). Использование слова «гранично-ранговый» подчеркивает способность кода исправлять ошибку в гранично-ранговой метрике.

Здесь существует граница для минимального гранично-рангового расстояния кода, похожего на границы Синглтона для расстояния Хэмминга:

Следствие 1. Если код C является линейным кодом длины п, размерности к и гранично-рангового расстояния d, то к + d <п + 1, п < т;                               (2)

кт + dn < (т + 1)п, п > т.                         (3)

Параметры (п, к, d) гранично-ранговых кодов

• 1)    Длина кодового вектора — п. Размер соответствующей кодовой матрицы - т х п.

• 2)    Число кодовых векторов или кодовых матриц — 2^пк.

• 3)    Кодовое расстояние d = п — к + 1.

• 4)    Код позволяет исправлять ошибки, граничный ранг которых равен или меньше t = [(d — 1)/2].

3.    Конструкция гранично-ранговых кодов

В гранично-ранговой метрике алгоритм кодирования работает над полем GF (2ⁿ). Пусть задан код (р, k,d), г де р - размер квадратной матрицы, d - кодовое гранично-ранговое расстояние, k - число ииформатщоініых векторов ( u o,..., U k—i)

Ui = (^0,..., up-1), г = 0,..., k — 1, где Uo,..., up-i - информационные символы.

Порождающая матрица кода имеет специальную форму:

S (до)

G =

S (91)

*

* *

S (дп-1)

к

S(gt) = ^Uj FS ,г = 0,...,n — 1. j=1

Для построения кода (р, k,d) сначала определим сопровождающую матрицу F_n. Пусть /(x) = xⁿ + /_n-ix^n-1 + • • • + /ix + /о примитивный многочлен над полем GF (2). Тогда сопровождающая матрица F_n имеет вид

F

n

0   10

0   01

• ••

• ••

• •               •. .

  / о / 1 ..

.. 00

.. 00

..... /n-Д

Порождающая матрица G задает код с гранично-ранговым расстоянием, не меньшим d, если выполняются условия: граничный ранг любой ненулевой матрицы Gt больше и равен d;

P(G^) > d или min d(Gt — Gj) = d.

t=3

Здесь выберем сопровождающую матрицу F_n так, чтобы p(G) > d. В этом случае код (р, k, d) является линейным.

Код (р, k, d") состоит из 2^nk матриц (gi , д2,..., д_пк ) над F2. Порождающие матрицы состоят из nk линейно независимых матриц.

Проверочная матрица Н, задающая код (р,k,d') с гранично-ранговым расстоянием, определяется из условия

Tr(G(H )^т ) = 0.

Матрица Н имеет размер n х n. Указанной порождающей матрице соответствует проверочная матрица вида

	H =	=	h 11 h 21 h 31	h 12 • • • h 22 • • • h 32 • • •	h 1 n h 2 n h 3 n	,		(4)
			••• hn1	••• ••• hn2    ‘ ‘ ‘	••• hnn
где элементы hi,h2,... ,hn из Проверочные матрицы	поля тоже	GF (2). состоят из			nk	линейно	независимых	матриц

(Ь1,һ2,...,Һпк )

4.    Коды в гранично-ранговой метрике, исправляющие одиночные решетчатые ошибки

Пусть передавалась кодовая матрица v = [«о «і ... v_n-i]- Пусть принята матрица y = v + е, где е - матрица ошибки.

Предполагаем, что все искаженные символы находятся в Тм столбце. Тогда матрицу ошибки можно представить в виде e=

/ 0

ео еі

0\

^еп - 1

Задача декодера - по известной матрице s найти матрицу ошибки е, а потом получить передававшуюся матрицу v. По построению, кодовая матрица v удовлетворяет равенствам

Tr( v h^T ) = 0, г = 0,..., пк.

Декодирование начинается с вычисления вектора синдрома s:

У = v + e ,

Tr ( у Н^т ) = Tr( v + е Н^т ), s = Tr( e H^т ),

⁽S 0 S 1 .. . З_п^ ) ^(й о ^z 1 . .. ^z^fc).

Можно считать, что элементы zg, zi,..., z_y-i € GF(q^m ) линейно независимы над GF(q). Следовательно, уравнение (5) может быть записано в виде

8г = Тг(УҺТ ), йг = Тг(еһт).

Таким образом, получена система из пк нелинейных уравнений относительно п неизвестных ео, еі,..., е_п-1. Важно отметить, что ошибочный столбец или строка ошибки неизвестны. Нужно найти одно решение, удовлетворяющее системе уравнений, потому что каждое решение из системы уранений ео,еі,..., е_п-і и йо, zi,..., z_n-i приводит к одному и тому же вектору ошибки е. Чтобы получить кодовую матрицу v, нужно поставить е в уравнение v = е + у.

5.    Пример. Код (4, 2,3)

Код (4, 2, 3) имеет вид

x

С =

y

x F 4 + y F2 x F2 + y F4

где x = (ж о ж і Ж 2 ж з ), у = (у о у і у 2 у з) - информационные вектор-строки длины 4. Здесь выберем сопровождающую матрицу F4 так, чтобы р(С) > 3. А матрица F4 - сопровождающая матрица многочлена ж⁴ + ж + 1:

F 4 =

Код (4, 2, 3) имеет общую формулу:

С =

Хо

У о

Х з + У 2

,Х2 + У о + У 3

Х1                     Х ₂                 Х 3

У 1                      У 2                 У з

Х 0 + Х з + У2 + У з Х 1 + У о + У з Х 2 + У 1

Х 2 + Х з + У о + У 1 + У з Х о + Х з + У 1 + У2  Х 1 + У 2 + У з

Дуальный код имеет вид

С ±

a F 4 + b F ₄² a F 4 + b F ₄ ⁴

a b

где a = (ао аі а2 аз), b = (Ьо bi Ь₂ Ьз) - произвольные вектор-строки длины 4.

Проверено, что

Ғг(С (С ±)т) = 0.

Код С состоит из 256 матриц над F₂. Порождающие матрицы состоят из 8 линейно независимых матриц, в качестве которых можно выбрать следующие, соответствующие выбору строк x и у:

	1	0	0	0		0	1	0	0		0	0	1	0		0	0	0	1
	0	0	0	0		0	0	0	0		0	0	0	0		0	0	0	0
91 =	0	1	0	0	; 9 2 =	0	0	1	0	; 9 з =	0	0	0	1	; 9 4 =	1	1	0	0
	0	0	1	0		0	0	0	1		1	1	0	0		0	1	1	0
	"0	0	0	0"		"0	0	0	0"		"0	0	0	0		"0	0	0	0"
	1	0	0	0		0	1	0	0		0	0	1	0		0	0	0	1
95 =	0	0	1	0	; 9 6 =	0	0	0	1	; 9 7 =	1	1	0	0	; 9 8 =	0	1	1	0
	1	1	0	0		0	1	1	0		0	0	1	1		1	1	0	1

Дуальный код состоит из 256 матриц. Для вычисления синдромов потребуется 8 линейно независимых над F2 матриц. Можно выбрать следующие 8 матриц, соответствующих выбору строк a 11 b:

	0001		1001		0100		0010
	0 0 10		0 0 11		10 0 1		0 10 0
^ 1 =	10 0 0	; ^ 2 =	0 10 0	; ^ з =	0 0 10	; ^ 4 =	0 0 0 1
	0000		0000		0000		0000
	"0 0 1 0"		"0 0 11"		"10 0 1"		"0  1 0 0"
	1001		1101		0110		0011
^ 5 =	0000	; ^ 6 =	0000	; 1 7 =	0000	; 1 8 =	0000
	1000		0100		0010		0001

1 1), у = (0110)

Тестирование: x =

- информационные вектор-строки. Из (9) была

передана кодовая матрица:

г =

1 0

.

Например матрица ошибки имеет вид:

0010 0010

0 0 0 0 0010

.             0

Полученная матрица у = v + е = о

V

Исправление ошибок

1	0	1
1	0	0
1	1	0
1	1	0

Шаг 1. Вычисление синдромов по 8 матрицам.

81 = Тт(уһ^ ) = 1; 82 = Тт(уһ^ ) = 1; S3 = 7>:уһ3) = 0; 84 = Тт(уһ^) = 1;

85 = Тт(уһ^) = 1; 86 = Тт(уһд ) = 1; 87 = Тт(уһ?) = 0; 88 = Тт(уһ§ ) = 1.

Шаг 2. Вычисление синдромов предполагаемой ошибки по 8 матрицам. Предполагаемая ошибка

/ Vi о о 0\

V2 0 0 0

V3 0 0 0

\ V4 0 0 0/

Расположение неправильное, так как:

vi = Тт(Vһf) = V3; V2 = Тт(Үһ2, ) = Vi; V3 = Тт(Vһ^) = V2; V4 = Тт(Vһ^ ) = 0;

V5 = Тт(Vһ^ ) = V2 + V4; V6 = Тт^) = V2; V7 = Тт(Vһ^ ) = Vi; V8 = Тт(VһІ) = 0.

Сравнивая v и 8ц находим, что система несовместна, так как Vi = 0,Vi = 1.

Шаг 3. Вычисление синдромов предполагаемой ошибки по 8 матрицам. Предполагаемая ошибка

/Wi W2 W3 W4 \ 0000 0     0     0     0    .

W =

⎝

Расположение неправильное, так как:

wi = Тт(Wһ^ ) = W4; W2 = Тт(Шһ^) = W1+W4; W3 = Тт(Wһ^) = W2; W4 = Тт(ШһХ ) = W3;

W5 = Тт(Wһ^ ) = W3; W6 = Тт(Wһ^) = W3 + W4;

W7 = Тт(Wһ^ ) = W1 + W4; W8 = Тт(Wһ^ ) = W2.

Сравнивая w^ и 8ц находим, что система несовместна, так как W2 = 0,W2 = 1.

Шаг 4. Вычисление синдромов предполагаемой ошибки по 8 матрицам. Предполагаемая ошибка

0 0 Ei 0

р _  0 0 E2  0

=  0 0 Ез 0 .

\ 0 0 Е4 0/

Расположение правильное, так как:

ti = Тт(ЕһГ) = Е2; t2 = Тт(Еһ[) = Е2; із = Тт(Еһ^) = Ез; І4 = Тт(ЕһІ) = Ei;

І5 = Тт(ЕһГ) = Е і ; іб = Тт(ЕһГ ) = Е і ; І7 = Тт(Еһ^) = Е2 + Е4; І8 = Тт(Еһ[) = Е2.

Сравнивая t^ и 8ц находим Е і = 1, Е2 = 1, Е3 = 0, Е4 = 1. Ошибка найдена правильно.

Кодовая матрица равна:

v = y + e =

1 1 0 + 0 0 0 0

1111 0110 0 110 1100

6.    Заключение

Таким образом, алгоритм декодирования гранично-ранговых кодов можно использовать для исправления ошибок. Однако иногда нужно заранее знать, какая строка или столбец повреждены. По данной причине последующая задача, которую предстоит решить, состоит в том, чтобы точно найти ошибочный столбец или строку матрицы ошибки.

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