Lab 04 Examples

Click <shift> <enter> in each code cell to run the code. Be sure to start with the #include directives to load the required libraries.

// For Lab 04, we are limited to these includes.
// Other libraries that can do the set or binary operations for us are not allowed.
// For example, DO NOT include <bitset> or <set>.

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

Lab 03 Solution (Hamming Code Transmitter)

const int BLOCK_SIZE = 8; // 7 bits + 1 extended parity bit (which we don't use for this Lab)

std::string data_str = "13"; // 13 base10 -> 1101 base2

int num = std::stoi(data_str);
std::vector<int> codeword(BLOCK_SIZE);

for (int i = BLOCK_SIZE - 1; i >= 1; i--) {

    if ((i & (i - 1)) == 0) {
        codeword[i] = 0;
    } else {                     // i = 7                   i = 6                i = 5            i = 3
        codeword[i] = (num & 1); // 1101 & 0001 = 1         110 & 001 =  0       11 & 01 = 1      1 & 1  = 1
        num = num >> 1;          // 1101 >> 1   = 110 (6)   110 >> 1  = 11 (3)   11 >> 1 = 1 (1)  1 >> 1 = 0
    }
}

for (int i = 1; i < BLOCK_SIZE; i = 1 << i) {
    for (int j = i; j < BLOCK_SIZE; j++) {
        if (j & i) {
            codeword[i] ^= codeword[j];
        }
    }
}

std::cout << "Original number: " << data_str << " Codeword: ";
for (int i = 1; i < codeword.size(); i++) {
    std::cout << codeword[i];
}

Original number: 13 Codeword: 1010101

Explanation of Bitwise Operations

• Binary Check for Powers of Two ((i & (i - 1)) == 0): This expression is true only when i is a power of two. It works because powers of two in binary have a single 1 bit, and subtracting 1 flips all lower bits, so the AND operation yields zero.

i (binary)	i-1 (binary)	i & (i-1)	Result
1000	0111	0000	0
0100	0011	0000	0
0010	0001	0000	0
0001	0000	0000	0

• Bit Shift in Loop Incrementation (i = 1 << i): This operation doubles the value of i each time, allowing the loop to visit each power of two (1, 2, 4, ...). This is important because parity bits in Hamming code are placed at positions that are powers of two.

• Isolating the Rightmost Bit (num & 1): The bitwise AND with 1 extracts the least significant bit of num. This is used to assign the next data bit to the codeword.

• Truncating the Rightmost Bit (num = num >> 1): The right shift operation moves all bits in num one place to the right, effectively removing the least significant bit. This prepares num for the next iteration, so the next data bit can be extracted.

• Calculating Parity Bits: The nested loops calculate the parity bits.

  • The i loop iterates over each parity bit index, while the inner j loop checks all indexes to see if they are members of the ith parity group.
  • The condition if (j & i) checks if the current bit index j contributes to the parity bit at index i. If the bitwise AND of j and i is non-zero, the bit at index j is in parity group i.
  • If the bit at index j is set in the codeword, it toggles the parity bit at index i using the XOR operation (codeword ^= i). This ensures that the parity bit reflects the correct parity for its group.

Base 10 to Base N Conversion (Repeated Division Method)

To convert a number from base 10 to another base (such as binary, octal, or hexadecimal), repeatedly divide the number by the target base, keeping track of the remainders. The remainders, read in reverse order (bottom up), give the digits of the number in the new base.

Example: Convert 156 (base 10) to base 2 (binary)

Division Step	Quotient	Remainder
156 ÷ 2	78	0
78 ÷ 2	39	0
39 ÷ 2	19	1
19 ÷ 2	9	1
9 ÷ 2	4	1
4 ÷ 2	2	0
2 ÷ 2	1	0
1 ÷ 2	0	1

Reading the remainders from last to first: 10011100 (binary)

int a = 17;
int b = 5;

// Integer division
int div = a / b; // Result: 3

// Remainder operator
int rem = a % b; // Result: 2

std::cout << a << " / " << b << " = " << div << std::endl;
std::cout << a << " % " << b << " = " << rem << std::endl;

17 / 5 = 3
17 % 5 = 2

Example: Base 10 to Base 16 Conversion (Hexadecimal)

Convert 9633 (base 10) to base 16 (hexadecimal) using the repeated division method. In hexadecimal, remainders greater than 9 are represented by letters (A=10, B=11, ..., F=15).

Division Step	Quotient	Remainder
9633 ÷ 16	602	1
602 ÷ 16	37	10 (A)
37 ÷ 16	2	5
2 ÷ 16	0	2

Reading the remainders from last to first: 25A1 (hexadecimal)