Member Avatar for Melissa111

Hello guys :)

I have a prog. assignment due on Sunday! I need help to get me started. The task is implement a program for any hamming codes not just (7,4). The user input the following:
1. Desired hamming code (n,k)
2. Choose to encode or decode.

So, I am thinking there will be a main function, encode function, decode function. and menu function. It will be neat to track errors using function rather than just writing everything in the main function, right!

Anyhow, I am somewhat confused and not understanding the basic concept of hamming codes. I could picture the source code layout but still can not start it. Can anyone help me to at least start????

Thanx
Mel

  • 6 Contributors
  • 7 Replies
  • 3K Views
  • 10 Months Discussion Span
  • Latest Post Latest Post by DMR
SpS commented: Throw Away Your Bad Habits +0

Dani AI

Generated

Good starting point is to pin down what pairs (n,k) are actually valid for binary Hamming codes. For the classic family, n = 2^m - 1 and k = n - m for some m >= 2; their minimum distance is 3, which is why they correct 1 bit and detect 2 bits (nice tie-in to ’s MHD comment). If the user types an arbitrary pair, validate it and explain why it is invalid. If you want SECDED, add a single overall parity bit to get the extended code (n+1, k).

’s R1/R2/R4 pattern generalizes cleanly: treat bit positions as 1-based; parity bit p (a power of two) covers all positions j whose binary index has that bit set, i.e., (j & p) != 0. That rule gives you both the encoder and the syndrome decoder.

Below is a compact, m-agnostic even-parity implementation sketch in C++ you can drop into your encode/decode functions. It uses 1-based indexing to match the textbook layout and avoids hard-coding (7,4).

#include <vector>
#include <stdexcept>

static inline bool isParityPos(int i) { return (i & (i - 1)) == 0; } // power of two

std::vector<int> hammingEncode(const std::vector<int>& u, int m) {
    int n = (1 << m) - 1, k = n - m;
    if ((int)u.size() != k) throw std::invalid_argument("bad message length");
    std::vector<int> cw(n + 1, 0); // 1..n
    for (int i = 1, di = 0; i <= n; ++i) if (!isParityPos(i)) cw[i] = u[di++];

    for (int p = 1; p <= n; p <<= 1) {
        int parity = 0;
        for (int j = 1; j <= n; ++j) if (j & p) parity ^= cw[j];
        cw[p] = parity; // even parity
    }
    return cw; // cw[1..n]
}

std::vector<int> hammingDecode(std::vector<int> cw, int m, int& correctedPos) {
    int n = (1 << m) - 1, s = 0;
    for (int p = 1; p <= n; p <<= 1) {
        int parity = 0;
        for (int j = 1; j <= n; ++j) if (j & p) parity ^= cw[j];
        if (parity) s |= p;
    }
    correctedPos = s; if (s) cw[s] ^= 1; // single-bit correction
    std::vector<int> u; u.reserve(n - m);
    for (int i = 1; i <= n; ++i) if (!isParityPos(i)) u.push_back(cw[i]);
    return u;
}

Tips: keep everything modulo 2, test by flipping each bit once to verify correction, and be explicit about even vs. odd parity in your menu. If you add the overall parity bit for SECDED, check it after computing the syndrome to flag double-bit errors.

Recommended Answers

All 7 Replies

Member Avatar for Acidburn

Fist best place to start is knowing what a hamming distance is, and how to get the MHD ... I assume for your menu you'll have a while loop ...

//whilst int x = 1
{
//do this
}

//whilst int x = 2
{
// do this
}

that could be your menu system. But for deffo you need the minuimn hamming distances for each code my friend.

Member Avatar for Gnome_101

Ok. hammering code, is a way of encoding a string of data, to ensure that the data will get from point a to point b saftely. It's an error prevention code, so that interfernce such as single bit errors cuased to a signal distrutption.

Hammering code works as follows.

Original code (in binary)

1 0 1 0 1 1 1 0 1 1 0

For Hammering code, you work with powers of 2
so 2 to the 0 is is 1
2 the 1st is 1
2 to the 2nd is 4
and so on, as long as your string allows.

There are check bits, which is how the hammering code allows for the check of errors

So....you have the following code

1 0 1 0 1 1 1 R8 0 1 1 R4 0 R2 R1

R1 check the parity (even parity) of everyother bit. So in other works, it check the parity of bits 1, 3, 5, 7, 9, 11, 13, 15, ect....

R2 check 2,3 skips 2 bits, checks 6,7 skips 2 and checks 10, 11 ect.

R4 checks 4,5,6,7, skips 4, checks 12,13,14,15 skip 4 ect

R8 checks bits 8,9,10,11,12,13,14,15, skips 8 and check the next 8 bits

For each power of 2 that you can have in the sting, that value is a check bit
which checks the 2 to the x value of bits, skips that amount, and checks the next amout in line.

Remember the the check bit, CHECKS IT'S SELF as well
ok so with out orignal code...

R1 check
1 0 1 0 1 1 1 R8 0 1 1 R4 0 R2 R1
1 0 1 0 1 1 1 R8 0 1 1 R4 0 R2 1 // R1 becomes a 1 becasue when checking the parity of the bits it checks, it finds there are 5 1's, to make it even, it becomes a 1 to make 6

R2 check
1 0 1 0 1 1 1 R8 0 1 1 R4 0 R2 1 // R2 found 5 1's and became a 1 to make even
1 0 1 0 1 1 1 R8 1 1 1 R4 0 1 1

R4 check
1 0 1 0 1 1 1 R8 1 1 1 R4 0 1 1
1 0 1 0 1 1 1 R8 1 1 1 1 0 1 1 // R4 changes

R8 check
1 0 1 0 1 1 1 R8 1 1 1 1 0 1 1
1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 // R8 changes

Now not every time are they going to change, but every time it looks to see the number of 1's in it's check pattern, and if working with even parity is going to changes according to the parity of it's check bits.

Hammering Code is efficent for detecting, and correcting errors after transmission.

If you have more questions I'll try to help out.

Member Avatar for Gnome_101

Fist best place to start is knowing what a hamming distance is, and how to get the MHD ... I assume for your menu you'll have a while loop ...

//whilst int x = 1
{
//do this
}

//whilst int x = 2
{
// do this
}

that could be your menu system. But for deffo you need the minuimn hamming distances for each code my friend.

the Distance to apply the hamming code...is this between check/redundacy bits? Or is this the amount of bits to check?

I just have theory from a class I'm in now...and would actually like to see how this is implemented.

Member Avatar for shisen

hi there...
i'd b very glad if u can plz send me the full code for (n,k)hamming code as i have been searching in the net but to no avail...i have to complete by next week...

Member Avatar for shisen

if by any chance u got the (n,k) hamming code..kindly mail them to me at ,urgently needed as submissions by next week...

commented: Throw away your bad habits +0
Member Avatar for DMR

> urgently needed as submissions by next week...
What makes you special?
http://www.daniweb.com/techtalkforums/announcement8-2.html

Noting also that this was 9 months old before you said "me too".

Agreed on both counts.

Due to the fact that the member who originally started this thread has not responded in quite a long time, this thread is considered abandoned and has been closed.

In accordance with our posting rules, other members having similar problems should start their own threads and post their questions there. In order to help us help you most quickly, please include as much information about your problem as possible in your posts.

If the member who originally started this thread wishes to have the thread reopened, please send your request, including a link to this thread, to one of our moderators via email or Private Message.

Thank you.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.