Перемножение битовых матриц. В чём ошибка?

Question

[Александр Семыкин]

Есть сообщение, закодированное линейным кодом (16,7). В коде могут содержаться ошибки, и для их определения мне нужно найти синдром. Делается это следующим образом: S = Ri x Ht, где:
- Ri - вектор принятого сообщения, длиной 16 бит.
- Ht - транспонированная проверочная матрица линейного кода размером 16x9.

Если в принятом слове нет ошибок, синдром должен быть равен 0. Проведя рассчёты в SageMath, я убедился в том, что всё работает отлично. При нулевом векторе ошибки синдром равен 0, при двух ошибках синдром позволяет их исправить.
Проблемы начинаются, когда я пытаюсь воплотить алгоритм в коде на Си:

static const uint16_t qr_16_7_check_matrix_T[16] = {
    0x4F,  // [0 0 1 0 0 1 1 1 1]
    0x11E, // [1 0 0 0 1 1 1 1 0]
    0x1B7, // [1 1 0 1 1 0 1 1 1]
    0x1E2, // [1 1 1 1 0 0 0 1 0]
    0x1C9, // [1 1 1 0 0 1 0 0 1]
    0xE5,  // [0 1 1 1 0 0 1 0 1]
    0x73,  // [0 0 1 1 1 0 0 1 1]
    0x100, // [1 0 0 0 0 0 0 0 0]
    0x80,  // [0 1 0 0 0 0 0 0 0]
    0x40,  // [0 0 1 0 0 0 0 0 0]
    0x20,  // [0 0 0 1 0 0 0 0 0]
    0x10,  // [0 0 0 0 1 0 0 0 0]
    0x8,   // [0 0 0 0 0 1 0 0 0]
    0x4,   // [0 0 0 0 0 0 1 0 0]
    0x2,   // [0 0 0 0 0 0 0 1 0]
    0x1,   // [0 0 0 0 0 0 0 0 1]
};

uint16_t qr_16_7_get_syndrome(uint16_t received_data) {
    uint16_t syndrome = 0x0;
    bool syndrome_bit = false;
    bool data_bit = false;
    bool matrix_bit = false;

    for (uint8_t cols = 0; cols < 9; cols++) {
        for (uint8_t rows = 0; rows < 16; rows++) {
            data_bit = (received_data >> rows) & 0x01;
            matrix_bit = (qr_16_7_check_matrix_T[rows] >> cols) & 0x01;
            syndrome_bit ^= data_bit & matrix_bit;
        }

        if (syndrome_bit) {
            syndrome |= (1 << cols);
        } else {
            syndrome &= ~(1 << cols);
        }
        syndrome_bit = false;
    }
    return syndrome & 0x01ff;
}

static const uint16_t qr_16_7_encoder[] = {
    0x0,    0x273,  0x4E5,  0x696,  0x9C9,  0xBBA,  0xD2C,  0xF5F,  0x11E2,
    0x1391, 0x1507, 0x1774, 0x182B, 0x1A58, 0x1CCE, 0x1EBD, 0x21B7, 0x23C4,
    0x2552, 0x2721, 0x287E, 0x2A0D, 0x2C9B, 0x2EE8, 0x3055, 0x3226, 0x34B0,
    0x36C3, 0x399C, 0x3BEF, 0x3D79, 0x3F0A, 0x411E, 0x436D, 0x45FB, 0x4788,
    0x48D7, 0x4AA4, 0x4C32, 0x4E41, 0x50FC, 0x528F, 0x5419, 0x566A, 0x5935,
    0x5B46, 0x5DD0, 0x5FA3, 0x60A9, 0x62DA, 0x644C, 0x663F, 0x6960, 0x6B13,
    0x6D85, 0x6FF6, 0x714B, 0x7338, 0x75AE, 0x77DD, 0x7882, 0x7AF1, 0x7C67,
    0x7E14, 0x804F, 0x823C, 0x84AA, 0x86D9, 0x8986, 0x8BF5, 0x8D63, 0x8F10,
    0x91AD, 0x93DE, 0x9548, 0x973B, 0x9864, 0x9A17, 0x9C81, 0x9EF2, 0xA1F8,
    0xA38B, 0xA51D, 0xA76E, 0xA831, 0xAA42, 0xACD4, 0xAEA7, 0xB01A, 0xB269,
    0xB4FF, 0xB68C, 0xB9D3, 0xBBA0, 0xBD36, 0xBF45, 0xC151, 0xC322, 0xC5B4,
    0xC7C7, 0xC898, 0xCAEB, 0xCC7D, 0xCE0E, 0xD0B3, 0xD2C0, 0xD456, 0xD625,
    0xD97A, 0xDB09, 0xDD9F, 0xDFEC, 0xE0E6, 0xE295, 0xE403, 0xE670, 0xE92F,
    0xEB5C, 0xEDCA, 0xEFB9, 0xF104, 0xF377, 0xF5E1, 0xF792, 0xF8CD, 0xFABE,
    0xFC28, 0xFE5B};

Я не могу обнаружить ошибку в коде, но значения, которые он выдаёт, неверные. По идее, для любого значения из словаря, приведённого выше, синдром должен быть равен 0. SageMath демонстрирует именно такие результаты. У меня же в половине случаев это не так. К примеру, для слов 0x1EBD или 0x2C9B значение синдрома равно 0x4E.

Answer 1

[Андрей]

Нумерация rows у Вас точно перепутана, т.е. Вы считаете матрицу с 0 до 15, а применять должны с 15 до 0. Насчет cols - я пока не разобрался.

P.S. И в целом, почему Вы операции производите именно побитово ? Ведь XOR отлично будет исполняться по 9 бит сразу.

Comments

[Александр Семыкин]

Всё верно, ошибка в порядке строк. В таком виде:
matrix_bit = (qr_16_7_check_matrix_T[15-rows] >> cols) & 0x01;
всё работает отлично.

Насчёт XOR: оно, конечно, будет выполняться по 9 бит сразу, но тогда мне надо сперва получить 9-битовое слово для этого, которого изначально нет. Это тоже вариант, я просто выбрал другой метод реализации.

[Андрей]

Извините, С не мой язык - мог что-то напутать в приведенном ниже коде, но теоретически Ваш алгоритм должен выглядеть так :

for (uint8_t rows = 0; rows < 16; rows++)
            if ((received_data >> rows) & 0x01)
                syndrome ^= qr_16_7_check_matrix_T[15-rows]

[Александр Семыкин]

Андрей: Верно, моя реализация была довольно наивной. Это решение куда изящнее. Спасибо за совет.