Добрый день! Помогите, пожалуйста! Нигде не могу найти описание кода Хемминга 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++): namespace hamming { typedef uint16_t hamming_word; enum error_type { NO_ERROR, SINGLE_BIT_ERROR, DOUBLE_BIT_ERROR }; inline uint8_t sum_bits(hamming_word n) { uint8_t sum = 0; while (n > 0) { if (n & 1) sum ^= 1; n >>= 1; } return sum; } hamming_word make_error(const hamming_word n, std::size_t position) { return n ^ 1 << position; } hamming_word hamming_encode(hamming_word i) { constexpr std::size_t matrix_cols = 15; hamming_word result = 0; uint16_t g[matrix_cols] = {0b10000000000, 0b01000000000, 0b00100000000, 0b00010000000, 0b00001000000, 0b00000100000, 0b00000010000, 0b00000001000, 0b00000000100, 0b00000000010, 0b00000000001, 0b11110101100, 0b01111010110, 0b00111101011, 0b11101011001}; for (std::size_t col = 0; col < matrix_cols; ++col) { result <<= 1; result |= sum_bits(i & g[col]); // Умножение двоичных векторов и сумма бит по модулю 2 } return result; } uint8_t syndrome(hamming_word codeword) { constexpr std::size_t matrix_rows = 4; hamming_word syndrome = 0; uint16_t h[matrix_rows] = { 0b111101011001000, 0b011110101100100, 0b001111010110010, 0b111010110010001}; for (std::size_t row = 0; row < matrix_rows; ++row) { syndrome <<= 1; syndrome |= sum_bits(codeword & h[row]); } return syndrome; } hamming_word hamming_error_correct(hamming_word i) { const uint8_t syndrome_to_bit[16] = {UINT8_MAX, 0, 1, 4, 2, 8, 5, 10, 8, 14, 9, 7, 6, 13, 11, 12 }; return i ^ 1 << syndrome_to_bit[syndrome(i)]; } hamming_word hamming_decode(hamming_word i) { uint8_t data = hamming_error_correct(i); return data >> 4 & 0x7FF; } void print_syndromes() { std::map<hamming_word, uint8_t> syndrome_map; for (int i = 0; i < 15; i++) { syndrome_map[i] = syndrome(1 << i); } for (auto it : syndrome_map) { std::cout << (int)it.second << "=>" << std::dec << (int)it.first << std::endl; } } }