Начальные сведения о помехозащищенном кодировании на основе кода Хэмминга

Помехозащищенное кодирование применяется для надёжной передачи данных по каналу связи, в котором может присутствовать источник помех. В МК 1986ВЕ8Т в качестве таких каналов связи выступают шины, осуществляющие передачу данных как между внутренними блоками МК, например, внутренняя память – ядро, так и между внутренними и внешними блоками, например, внешняя память – ядро. Само помехозащищенное кодирование, а также декодирование с коррекцией ошибок, осуществляется на аппаратном уровне с помощью специальных блоков. В качестве используемого самокорректирующегося кода применяется код Хэмминга, при этом в МК используется всего два вида кодовых слов: (7,4) для задания режима работы и (72,64) для внутренней памяти и памяти на внешней шине.

Общий алгоритм коррекции ошибок (ECC), основанный на коде Хэмминга, на примере операции записи/чтения:

1. Запись слова А:
   1. Кодирование исходного слова А. На основании записываемых данных (для слов (72,64) также используется адрес) вычисляется проверочные (контрольные) биты ECC, которые передаются на запись совместно с исходным словом А.
   2. Запись слова А вместе с контрольными битами ECC.
2. Чтение слова А:
   1. Чтение слова А совместно с контрольными битами ECC.
   2. На основании данных (для (72,64) адреса) слова А производится повторный расчёт контрольных бит ECC.
   3. Сравнение считанных проверочные бит ECC с заново рассчитанными. Если проверочные биты совпадают, значит ошибок нет, ECC биты отбрасываются и исходное слово А передаётся дальше на чтение.
   4. Если проверочные биты не совпадают и имеет место одиночная ошибка, то происходит её исправление, операция чтения при этом также успешно выполняется. Если обнаружена двойная ошибка, или более, то данные не восстанавливаются, и происходит ошибка чтения.

Здесь мы рассмотрим построение кода Хэмминга 7,4, чтобы понять, как производится генерация ECC и коррекция одиночных ошибок.

Однако, прежде чем мы приступим к рассмотрению кода Хэмминга (7,4), сделаем небольшое отступление и рассмотрим задачу о надёжной передаче данных в ненадёжном канале связи и разберёмся, откуда появилось условие для кода Хэмминга 2^k>=k+m+1.

Небольшое отступление

Предположим, что мы хотим передать слово B={b0,b1,b2} по каналу связи, в котором действует источник помех (не такая уж и гипотетическая задача). Предположим, что при передаче слова В источник помех может вызвать ошибку не более чем в 1 бите. Передавать слово В в исходном виде дело совершенно не надёжное, и установить, что же в итоге мы хотели передать, будет невозможно. Один из тривиальных способов защиты информации в данном канале: утроить все биты исходного слова (а-ля троированная логика) В’={b0,b0,b0, b1,b1,b1, b2,b2,b2}. Тогда, если при передаче изменится один из битов, то по схеме мажорирования (по принципу большинства), можно восстановить слово В’, а значит, и исходное слово В. Такое решение при передаче данных является некорректным, так как утроение бит приведёт к тому, что в таком длинном слове вероятность появления двойных ошибок резко возрастёт, а исправить их уже не получится. Поэтому необходимо закодировать исходное слово так, чтобы увеличение его длины было минимальным.

Это как раз и сделал Ричард Хэмминг. Он рассмотрел случай, когда при передаче может возникнуть 1 ошибка, и пришёл к выводу, что, передавая закодированное слова длины l = m+k, где m – длина исходного слова, k – длина контрольных бит. Приёмник, с учётом одной ошибки, может получить l+1 различных вариантов передаваемого слова. Например, предаём слово C= {k0, k1, m0} длиной 3 бита. До приёмника могут дойти следующие слова:

• {k0, k1, m0} – нет ошибки;
• {k0*, k1, m0} – ошибка в k0;
• {k0, k1*, m0} – ошибка в k1;
• {k0, k1, m0*} – ошибка в m0.

Итого l+1=4 различных варианта принятого слова. Чтобы закодировать с помощью контрольных бит все эти случаи, необходимо чтобы 2^k>=l+1 или 2^k >= m+k+1. Вот так и появилось знаменитое неравенство для нахождения количества контрольных бит k в зависимости от необходимого количества бит m исходного слова.

Для надёжной передачи 4 бит информации (m), исходя из выше указанного неравенства, необходимо к ним добавить ещё 3 проверочных бита (k).

В обозначении 7,4 первое число (7) определяет количество бит закодированного слова, второе (4) – количество бит исходного слова.

Пусть имеется исходное слово A = (a3, a2, a1, a0). Для возможности исправить единичную ошибку с помощью кодирования Хэмминга необходимо вычислить контрольные биты ЕСС на основании исходного слова, которые будут передаваться совместно со словом А. Таким образом, в результате кодирования получится слово X = (r2, r1, r0, a3, a2, a1, a0), где r[2:0] – проверочные (контрольные) биты ECC.

Вычисление проверочных разрядов r[2:0] выполняется по формулам:

r2 = a3 ⊕ a2 ⊕ a1;

r1 = a3 ⊕ a2 ⊕ a0;

r0 = a3 ⊕ a1 ⊕ a0,

⊕ - сложение по модулю 2.

Данные уравнения для проверочных бит подобраны таким образом, чтобы каждый проверочный бит r зависел сразу от нескольких бит a исходного слова. При этом, изменение одного бита исходного слова вызовет изменение как минимум двух проверочных бит. По этим изменениям и определяется ошибка.

Для математического описания кодирования и декодирования исходных слов вводят специальные матрицы: матрицу G генерации и матрицу H проверки.

Матрица генерации G формирует закодированное слово путём перемножения слова A и матрицы генерации G.

X = AG, при этом операция суммирования производится по модулю 2.

Для тех, кто не может сразу вспомнить как выполняется перемножение матриц, а со мной такое случается, привожу небольшую подсказку:

При перемножении матриц для кодирования Хэмминга вместо «+» используется ⊕.

Матрица G для кода 7,4 выглядит следующим образом:

Операция перемножения A на G:

Таким образом перемножив A на G мы получим закодированное слово X, состоящее из слова A и проверочных бит r[2:0].

При чтении закодированного слова X заново выполняется расчёт контрольных бит на основе слова А, а затем вычисленные и считанные контрольные биты складываются по модулю 2. Результат сложения образует так называемый синдром S = {S2, S1, S0}. По синдрому определяется ошибка, если таковая была.

S2 = r2 ⊕ r2’ = r2 ⊕ a3 ⊕ a2 ⊕ a1;

S1 = r1 ⊕ r1’ = r1 ⊕ a3 ⊕ a2 ⊕ a0;

S0 = r0 ⊕ r0’ = r0 ⊕ a3 ⊕ a1 ⊕ a0;

где r[2:0]’ – заново вычисленные проверочные биты на основе считанного слова А.

Для расчёта синдрома S[2:0], аналогично матрицы генерации G, вводят проверочную матрица H. Синдром формируется путём перемножения считанного слова X и транспонированной проверочной матрицы H^T:

S = X H^T.

Проверочная матрица H для кода Хэмминга 7,4 имеет вид:

Каждая строка этой таблицы при побитом перемножении на слово X образует соответствующий бит синдрома.

Если поменять местами строки 1 и 3, то получим проверочную матрицу, указанную в спецификации, при этом изменится порядок следования бит синдрома S = {S0, S1, S2}:

Операция перемножения X на H^T (H матрица как в спецификации):

По получившемуся вектору синдрома и проверочной матрице H можно определить, где произошла ошибка. Если ошибки не было, то синдром равен 0: S = (0, 0, 0). Если же произошла одиночная ошибка, то совпадающий с синдромом столбец указывает на ошибочный бит:

Так, например, если синдром S = (0, 1, 0), значит ошибка произошла в r1, если S = (0, 1, 1), то ошибка в a2. Определив по синдрому ошибочный бит, инвертируем его, чтобы восстановить исходное слово.

К сожалению, данный код Хэмминга (7,4) может применяться только в условиях возникновения однократных ошибок. Если произойдет две и более ошибки, то отличить их от одинарной не получится, а поэтому в данном случае исправление одной ошибки не приведёт к восстановлению исходного слова.

Чтобы этого избежать, вводят дополнительный бит четности p (parity), с помощью которого можно определить, произошла одиночная ошибка либо двойная и более. Тогда, если имеет место однократная ошибка, слово можно исправить, если двукратная – слово восстановлению не подлежит.

Бит чётности может занимать любую позицию в закодированном слове, но для определённости мы сделаем, как указано в спецификации, и добавим его на место 4 бита. При этом закодированное слово X приобретёт вид:

X = (r2, r1, r0, p, a3, a2, a1, a0);

Бит чётности p вычисляется на основе всех остальных бит слова X путём их сложения по модулю 2:

p = r2 ⊕ r1 ⊕ r0 ⊕ a3 ⊕ a2 ⊕ a1 ⊕ a0.

При определении ошибки заново вычисляется бит чётности p’ и складывается со считанным битом p, при это данный результат будет являться новым битом синдрома. Так как мы добавили бит чётности на 0 позицию проверочных бит, то слово синдрома S = {S0, S1, S2, S3} приобретёт следующий вид:

S0 = p ⊕ p’ = p + r2 ⊕ r1 ⊕ r0 ⊕ a3 ⊕ a2 ⊕ a1 ⊕ a0;

S1 = r0 ⊕ r0’ = r0 ⊕ a3 ⊕ a1 ⊕ a0;

S2 = r1 ⊕ r1’ = r1 ⊕ a3 ⊕ a2 ⊕ a0;

S3 = r2 ⊕ r2’ = r2 ⊕ a3 ⊕ a2 ⊕ a1;

С учётом бита чётности проверочная матрица H будет иметь вид:

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

Для кода Хэмминга (72,64) генерации ECC и коррекция ошибок осуществляется точно таким же образом, просто используемые матрицы немного больше. Надо заметить, что для кода (72, 64) расстояние Хэмминга позволяет определять двойные ошибки, а потому бит чётности в данном коде не используется.

В спецификации приведён пример программного вычисления проверочных бит ЕСС для кода Хэмминга (72, 64). Как уже было отмечено ранее, в данном коде не используется бит чётности, поэтому алгоритм вычисления ECC для кода (7,4) с битом чётности будет отличаться от алгоритма для кода (72,64). В связи с этим мы разберём здесь программную реализацию вычисления ECC для кода (7,4) c битом чётности на примере вычисления бит CFGx в режимах запуска EXTBUS_CFG+JB и EXTBUS_CFG+JA.

Процесс вычисления проверочных бит заключается в перемножении исходного слова А на матрицу генерации ECC, которой является правая часть проверочной матрицы H.

Полный код функции представлен ниже:

Gen_ECC.c

uint8_t Gen_ECC(uint8_t data)
{
	uint8_t G[] = {0, 0xB,0xD,0xE}; // матрица генерации
	uint8_t i = 0, j = 0, res = 0, inputw = 0;
	
	data = data & 0xF;
	
	for (i=1; i<4; i++) // Формируем r3-r1
        {
          inputw = data & G[i];  // Выбрали необходимые информационные биты для формирования контрольного бита
          res=0;
          for (j=0; j<4; j++)
	      res = res ^ ((inputw >> j) & 0x01);   // Суммируем выбранные информационные биты по модулю 2, получаем один контрольный бит		
	  data |= res<<(i+4); // Дописываем контрольные биты к исходному слову
        }
		
	res=0; //Формируем бит чётности p
	for (j=0; j<8; j++)
	   res = res ^ ((data >> j) & 0x01);   // Суммируем все биты получившегося слова для нахождения бита чётности (S0)
	
	return data |= res<<4;	
}

Разберём основные части.

Для начала составим из правой части проверочной матрицы H массив генерации ECC G[], при этом каждый элемент данного массива будет представлять строку правой части матрицы H. Далее в цикле формируем проверочные биты, путем выборки необходимые информационные биты, а именно, накладывая маску из массива генерации, после чего суммируем их по модулю два. Делаем это для трёх проверочных бит. Дописываем их к информационным битам. После вычисляем бит чётности p суммированием по модулю два всех проверочных и информационных бит, и дописываем его в кодируемое слово. Исходное слово закодировано.

Получившаяся таблица для всех значений бит CFGx[3:0]: