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

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

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

Bitset decoder::decode(const Bitset &amp; 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. Так вот, даже здесь прослеживается, что алгоритм плывет и не позволяет физически получить индекс третьего бита, соответственно исправить. введите сюда описание изображения

Kiriruso
  • 11
  • 3
  • вместо std::vector используйте std::bitset , вместо pow(2, degree) используйте 1 << degree , и реализация будет легче и быстрее. – AR Hovsepyan Mar 17 '22 at 05:47

1 Answers1

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}; // Важно вычесть единичку
    }
Kiriruso
  • 11
  • 3