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

Тема в разделе "WASM.CRYPTO", создана пользователем coshmarik, 1 май 2010.

  1. coshmarik

    coshmarik New Member

    Публикаций:
    0
    Регистрация:
    30 апр 2010
    Сообщения:
    7
    Добрый день!
    Помогите, пожалуйста!
    Нигде не могу найти описание кода Хемминга 15/11.
    Заранее большое спасибо!
     
  2. OLS

    OLS New Member

    Публикаций:
    0
    Регистрация:
    8 янв 2005
    Сообщения:
    322
    Адрес:
    Russia
    Считаем биты в сообщениях с единицы, обозначим "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

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

    coshmarik New Member

    Публикаций:
    0
    Регистрация:
    30 апр 2010
    Сообщения:
    7
    Очень-очень большое спасибо!!!
     
  4. Dr.Golova

    Dr.Golova New Member

    Публикаций:
    0
    Регистрация:
    7 сен 2002
    Сообщения:
    348
    А теперь хочется узнать про XOR таблицы, кои используются во всех современных архиваторах для восстановления данных. Это вроде не совсем коды хемминга - тут нужен некий брутфорс узлов, с вероятностным успехом. или не?
     
  5. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Dr.Golova
    вроде в архиваторах везде простой КСОР с весами
    1 1 1 1 ... На этот счет есть статья з0мби доходчивая...

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

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

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

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Вопщем, в программах формула такая:

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

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

    Aoizora Active Member

    Публикаций:
    0
    Регистрация:
    29 янв 2017
    Сообщения:
    351
    Древний тред, нашел его, пока искал реализации кода Хэмминга (15, 11). Нормальных реализаций нет, пришлось писать свою :) Все матрицы расчитывал вручную на бумаге


    Код (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. }
     
    q2e74 нравится это.