algorithms-and-data-structures/algorithms/coding/hammingCode.cpp at main · evevseev/algorithms-and-data-structures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include "string"
#include "cmath"
#include "sstream"

uint16_t get_parity_bits_count(size_t msg_len) {
    if (msg_len == 1) {
        return 1;
    }

    uint16_t p = static_cast<uint16_t>(log2(msg_len + 1));

    return p;
}

std::string hammingCodeEncode(const std::string &s) {
    if (s.emplty()) {
        return ""
    }

    uint16_t parity_bits_count = std::log2(s.size()) + 1;

    size_t str_ptr = 0;
    uint64_t parity_bits_val = 0;

    for (size_t i = 1; i < s.size() + 1 + parity_bits_count; ++i) {
        if ((i & (i - 1)) != 0 && s[str_ptr++] == '1') {  // if not power of 2 and s[i] == '1'
            parity_bits_val ^= i;
        }
    }

    std::stringstream ss;
    str_ptr = 0;
    for (size_t i = 1; i < s.size() + 1 + parity_bits_count; ++i) {
        if ((i & (i - 1)) == 0) {  // if power of 2
            ss << (((parity_bits_val & i) == i) ? '1' : '0');
        } else {
            ss << s[str_ptr++];
        }
    }

    return ss.str();
}

std::string hammingCodeDecode(const std::string &s) {
    std::stringstream ss;
    uint64_t parity_bits_val = 0;

    for (size_t i = 1; i < s.size() + 1; ++i) {
        if (s[i - 1] == '1') {
            parity_bits_val ^= i;
        }
    }

    for (size_t i = 1; i < s.size() + 1; ++i) {
        if ((i & (i - 1)) != 0) {  // if not power of 2
            char ch = s[i - 1];
            if (parity_bits_val == i) {  // if error occurred on this index
                ch = (ch == '1' ? '0' : '1');
            }
            ss << ch;
        }
    }

    return ss.str();
}