Код Хемминга 15/11

Добрый день!
Помогите, пожалуйста!
Нигде не могу найти описание кода Хемминга 15/11.
Заранее большое спасибо!

 

Считаем биты в сообщениях с единицы, обозначим "p" - исходное сообщение, "с" - кодированное (т.е. в нашем случае нумерация - p1..p11, c1..c15).

Все биты кодированного сообщения, номера которых - точная степень двойки (c1, c2, c4, c8) - контрольные, остальные - это биты сообщения (т.е. c3<-p1, c5<-p2, c6<-p3, c7<-p4, c9<-p5, далее - без пропусков).

Каждый контрольный бит отвечает за чётность суммы группы бит, в номерах каждого из которых этот бит поднят.
Т.е.чтобы определить, какие контрольные биты контролируют бит кодированного сообщения в позиции k надо разложить k по степеням двойки: если k = 11 = 8 + 2 + 1, то этот бит контролируется c1, c2 и c8.

В итоге контрольные биты для Hamming(15,11) вычисляются как

c1 <- c3+c5+c7+c9+c11+c13+c15
c2 <- c3+c6+c7+c10+c11+c14+c15
c4 <- c5+c6+c7+c12+c13+c14+c15
c8 <- c9+c10+c11+c12+c13+c14+c15

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

 

Очень-очень большое спасибо!!!

 

А теперь хочется узнать про XOR таблицы, кои используются во всех современных архиваторах для восстановления данных. Это вроде не совсем коды хемминга - тут нужен некий брутфорс узлов, с вероятностным успехом. или не?

 

Dr.Golova
вроде в архиваторах везде простой КСОР с весами
1 1 1 1 ... На этот счет есть статья з0мби доходчивая...

А вот quickpar и iceecc юзают таблицы для КСОРа с 16битными весами,
это гораздо круче.

То бишь архиваторы исправляют однократные ошибки на срез, а quickpar соответственно 65536 кратные.

А в проге persicum's CRC32 веса так ващще 32битные и исправляет она миллионнократные ошибки.

 

Вопщем, в программах формула такая:

w1*byte1 XOR w2*byte2 XOR w3*byte3... = parity1
и т.д.

В архиваторах веса просто единицы, а в специализированных прогах- вовсе не единицы.
Нулей в весах нет, в отличие от кодов хэмминга...

 

Древний тред, нашел его, пока искал реализации кода Хэмминга (15, 11). Нормальных реализаций нет, пришлось писать свою Все матрицы расчитывал вручную на бумаге

Code (C++):

1. namespace hamming
2. {
3.     typedef uint16_t hamming_word;
4.  
5.     enum error_type
6.     {
7.         NO_ERROR,
8.         SINGLE_BIT_ERROR,
9.         DOUBLE_BIT_ERROR
10.     };
11.  
12.     inline uint8_t sum_bits(hamming_word n)
13.     {
14.         uint8_t sum = 0;
15.         while (n > 0)
16.         {
17.             if (n & 1)
18.                 sum ^= 1;
19.             n >>= 1;
20.         }
21.         return sum;
22.     }
23.  
24.     hamming_word make_error(const hamming_word n, std::size_t position)
25.     {
26.         return n ^ 1 << position;
27.     }
28.  
29.     hamming_word hamming_encode(hamming_word i)
30.     {
31.         constexpr std::size_t matrix_cols = 15;
32.         hamming_word result = 0;
33.  
34.         uint16_t g[matrix_cols] = {0b10000000000,
35.                                    0b01000000000,
36.                                    0b00100000000,
37.                                    0b00010000000,
38.                                    0b00001000000,
39.                                    0b00000100000,
40.                                    0b00000010000,
41.                                    0b00000001000,
42.                                    0b00000000100,
43.                                    0b00000000010,
44.                                    0b00000000001,
45.                                    0b11110101100,
46.                                    0b01111010110,
47.                                    0b00111101011,
48.                                    0b11101011001};
49.  
50.         for (std::size_t col = 0; col < matrix_cols; ++col)
51.         {
52.             result <<= 1;
53.             result |= sum_bits(i & g[col]); // Умножение двоичных векторов и сумма бит по модулю 2
54.         }
55.  
56.         return result;
57.     }
58.  
59.     uint8_t syndrome(hamming_word codeword)
60.     {
61.         constexpr std::size_t matrix_rows = 4;
62.         hamming_word syndrome = 0;
63.  
64.         uint16_t h[matrix_rows] = { 0b111101011001000,
65.                                     0b011110101100100,
66.                                     0b001111010110010,
67.                                     0b111010110010001};
68.  
69.         for (std::size_t row = 0; row < matrix_rows; ++row)
70.         {
71.             syndrome <<= 1;
72.             syndrome |= sum_bits(codeword & h[row]);
73.         }
74.  
75.         return syndrome;
76.     }
77.  
78.     hamming_word hamming_error_correct(hamming_word i)
79.     {
80.         const uint8_t syndrome_to_bit[16] = {UINT8_MAX, 0, 1, 4, 2, 8, 5, 10, 8, 14, 9, 7,  6, 13, 11, 12  };
81.  
82.         return i ^ 1 << syndrome_to_bit[syndrome(i)];
83.     }
84.  
85.     hamming_word hamming_decode(hamming_word i)
86.     {
87.         uint8_t data = hamming_error_correct(i);
88.         return data >> 4 & 0x7FF;
89.     }
90.  
91.     void print_syndromes()
92.     {
93.         std::map<hamming_word, uint8_t> syndrome_map;
94.  
95.         for (int i = 0; i < 15; i++)
96.         {
97.             syndrome_map[i] = syndrome(1 << i);
98.         }
99.  
100.         for (auto it : syndrome_map)
101.         {
102.             std::cout << (int)it.second << "=>" << std::dec << (int)it.first << std::endl;
103.         }
104.     }
105. }