1

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

// Bitset - это std::vector<bool>
int decoder::numberControlBits(const Bitset & bitset) {
        int degree = 0;
        while (pow(2, degree) < bitset.size())
            degree += 1;
        return degree - 1;
    }

    bool decoder::isCorrectBit(const Bitset & bitset, int degree) {
        bool control = false;
        int bit = (int)pow(2, degree) - 1;
        for (int begin = bit, end = begin + bit; begin < bitset.size(); begin += (int)pow(2, degree) * 2, end = begin + bit) {
            if (end > bitset.size() - 1)
                end = bitset.size() - 1;
            for (int j = begin; j <= end; ++j)
                control ^= bitset[j];
        }
        control ^= bitset[bit]; // исключаю начальный бит, так как он включен в расчет
        return control == bitset[bit];
    }

    void decoder::flip(Bitset & bitset, int degree) {
        int bit = (int)pow(2, degree) - 1;
        bitset[bit].flip();
    }

    std::pair<int, bool> decoder::searchBitDistortion(const Bitset & bitset) {
        int index = 0;
        bool isDistortion = false;
        for (int i = 0; i <= numberControlBits(bitset); ++i) {
            if (!isCorrectBit(bitset, i)) {
                index += i;
                isDistortion = true;
            }
        }
        return {index, isDistortion};
    }

    Bitset decoder::decode(const Bitset & bitset) {
        Bitset result = bitset;
        auto [index, isDistortion] = searchBitDistortion(result);
        if (isDistortion) 
            result[index].flip();
        return result;
    }

Проблема заключается в том, что алгоритм исправляет верно только тогда, когда искажение происходит в 0 или 1 бите, в остальных случаях алгоритм не может определить нужный бит. В методе searchBitDistortion определяю бит, который необходимо исправить.

Пробовал руками пересчитывать, при нумерации битов с 0 алгоритм не работает, при нумерации с 1 алгоритм работает... Из-за этого у меня возникает некоторый диссонанс и не могу осознать, как же так устроить проход по битам.

Чтобы стало понятнее приведу пример.

Входное сообщение:         0100010000111101
Сообщение после кодировки: 100110000100001011101
Например исказился 3 бит:  101110000100001011101

На картинке будет расчет первых двух контрольных битов, так как только их сумма отвечает за 3 бит кодового сообщения. Первая строка - это сообщение с искаженным 3 битом, вторая и третья соответственно нумерация с 0 и 1. Первый расчет для нумерации с 0, второй для нумерации с 1. Так вот, даже здесь прослеживается, что алгоритм плывет и не позволяет физически получить индекс третьего бита, соответственно исправить. введите сюда описание изображения

1
  • вместо std::vector<bool> используйте std::bitset , вместо pow(2, degree) используйте 1 << degree , и реализация будет легче и быстрее. 17 мар 2022 в 5:47

1 ответ 1

0

Разобрался со своей проблемой. Суть в том, что я добавлял не двойку в степени к индексу, а сами степени. Код с ошибкой:

        for (int i = 0; i <= numberControlBits(bitset); ++i) {
            if (!isCorrectBit(bitset, i)) {
                index += i; // <- Здесь неверно добавляю сами степени.
                isDistortion = true;
            }
        }

Необходимо было лишь исправить расчет индекса, следующим образом:

std::pair<int, bool> decoder::searchBitDistortion(const Bitset & bitset) {
        int index = 0;
        bool isDistortion = false;
        for (int i = 0; i <= numberControlBits(bitset); ++i) {
            if (!isCorrectBit(bitset, i)) {
                index += (int)pow(2, i); // OK!
                isDistortion = true;
            }
        }
        return {index - 1, isDistortion}; // Важно вычесть единичку
    }
1
  • (int)pow(2, i); // OK! — это не OK, и вот почему: 1, 2, 3.
    – wololo
    28 мар 2022 в 17:29

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.