Инструменты пользователя

Инструменты сайта


prog:spec:hammingcode

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

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

Общий алгоритм генерации ECC и коррекции ошибок на основе кода Хэмминга

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

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

Начальная информация о коррекции ошибок на основе кода Хэмминга 7,4

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

Однако, прежде чем мы приступим к рассмотрению кода Хэмминга (7,4), сделаем небольшое отступление и рассмотрим задачу о надёжной передаче данных в ненадёжном канале связи и разберёмся, откуда появилось условие для кода Хэмминга 2k>=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 различных варианта принятого слова. Чтобы закодировать с помощью контрольных бит все эти случаи, необходимо чтобы 2k>=l+1 или 2k >= 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 = a3a2a1;

r1 = a3a2a0;

r0 = a3a1a0,

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

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

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

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

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


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

 Перемножение вектора А на матрицу В


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

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

 Матрица генерации для кода Хэмминга 7,4

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

 Перемножение вектора А на матрицу G

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

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

S2 = r2 ⊕ r2’ = r2 ⊕ a3a2a1;

S1 = r1 ⊕ r1’ = r1 ⊕ a3a2a0;

S0 = r0 ⊕ r0’ = r0 ⊕ a3a1a0;

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

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

S = X HT.

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

 Проверочная матрица для кода Хэмминга 7,4 (S2,S1,S0)

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

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

 Проверочная матрица для кода Хэмминга 7,4 (S0,S1,S2)

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

 Перемножение вектора X на матрицу H

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

 Проверочная матрица для кода Хэмминга 7,4 (S0,S1,S2)

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

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

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

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

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

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

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

p = r2 ⊕ r1 ⊕ r0 ⊕ a3a2a1a0.

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

S0 = p ⊕ p’ = p + r2 ⊕ r1 ⊕ r0 ⊕ a3a2a1a0;

S1 = r0 ⊕ r0’ = r0 ⊕ a3a1a0;

S2 = r1 ⊕ r1’ = r1 ⊕ a3a2a0;

S3 = r2 ⊕ r2’ = r2 ⊕ a3a2a1;

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

 Проверочная матрица для кода Хэмминга 7,4 c битом чётности (S1,S2,S3,S0)

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

 Проверочная матрица для кода Хэмминга 7,4 c битом чётности (S1,S2,S3,S0)

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

Программная генерация ECC

В спецификации приведён пример программного вычисления проверочных бит ЕСС для кода Хэмминга (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]:

Закодированное слово Проверочные биты ECC Информационные биты CFGx
0x00 0000 0000
0x71 0111 0001
0xB2 1011 0010
0xC3 1100 0011
0xD4 1101 0100
0xA5 1010 0101
0x66 0110 0110
0x17 0001 0111
0xE8 1110 1000
0x99 1001 1001
0x5A 0101 1010
0x2B 0010 1011
0x3C 0011 1100
0x4D 0100 1101
0x8E 1000 1110
0xFF 1111 1111
prog/spec/hammingcode.txt · Последние изменения: 2019/03/19 18:25 — vova