H.
3 Reed–Muller Codes
(a) R(1,4)
The code R(1,4) consists of the evaluation vectors of all Boolean polynomials of degree at
most 1 in four variables. Its parameters are n = 16 and k = 1 + 4 = 5, so it contains 32
codewords.
In the program, a basis corresponding to {1, x₁, x₂, x₃, x₄} is constructed and all linear
combinations are generated, producing all codewords of R(1,4).
(b) Dual of R(1,3)
For R(1,3), n = 8 and k = 4. All 16 codewords are generated from the basis {1, x₁, x₂, x₃}.
The binary inner product between every pair of codewords is zero, showing that the code is
self-orthogonal. Since k = n/2, it follows that R(1,3) is self-dual.
(c) Weight enumerator of R(2,3)
The code R(2,3) consists of all Boolean polynomials of degree at most 2 in three variables
and has parameters n = 8 and k = 7. All 128 codewords are generated and their Hamming
weights are counted.
The resulting weight distribution is:
1 codeword of weight 0, 28 of weight 2, 70 of weight 4, 28 of weight 6, and 1 of weight 8.
Thus, the weight enumerator is:
1 + 28z² + 70z⁴ + 28z⁶ + z⁸.
Code:
#include <stdio.h>
#include <stdint.h>
//Hamming weight
int weight(uint16_t x) {
int w = 0;
while (x) {
w += x & 1;
x >>= 1;
}
return w;
}
/* --------------------------------------------------
PART A: Generate all codewords of R(1,4)
-------------------------------------------------- */
void solve_part_a() {
printf("--- Part A: Codewords of R(1,4) ---\n");
int m = 4;
int n = 1 << m; // length = 16
int k = 1 + m; // dimension = 5
// Basis: 1, x1, x2, x3, x4
uint16_t basis[5] = {0};
// Constant polynomial 1 → all-ones vector
basis[0] = 0xFFFF;
// Coordinate functions
for (int col = 0; col < n; col++) {
if ((col >> 3) & 1) basis[1] |= (1 << col); // x1
if ((col >> 2) & 1) basis[2] |= (1 << col); // x2
if ((col >> 1) & 1) basis[3] |= (1 << col); // x3
if ((col >> 0) & 1) basis[4] |= (1 << col); // x4
}
// Generate all 2^5 = 32 codewords
for (int i = 0; i < (1 << k); i++) {
uint16_t cw = 0;
for (int j = 0; j < k; j++) {
if ((i >> j) & 1) {
cw ^= basis[j];
}
}
// Print codeword
printf("c[%02d]: ", i);
for (int bit = 0; bit < n; bit++) {
printf("%d", (cw >> bit) & 1);
}
printf("\n");
}
printf("\n");
}
/* --------------------------------------------------
PART B: Full verification that R(1,3) is self-dual
-------------------------------------------------- */
void solve_part_b() {
printf("--- Part B: Dual Verification of R(1,3) ---\n");
int m = 3;
int n = 1 << m; // length = 8
int k = 1 + m; // dimension = 4
uint8_t basis[4] = {0};
// Constant polynomial 1
basis[0] = 0xFF;
// Coordinate functions
for (int col = 0; col < n; col++) {
if ((col >> 2) & 1) basis[1] |= (1 << col);
if ((col >> 1) & 1) basis[2] |= (1 << col);
if ((col >> 0) & 1) basis[3] |= (1 << col);
}
// Generate all codewords
uint8_t codewords[16];
for (int i = 0; i < (1 << k); i++) {
uint8_t cw = 0;
for (int j = 0; j < k; j++) {
if ((i >> j) & 1) {
cw ^= basis[j];
}
}
codewords[i] = cw;
}
// Check orthogonality of all pairs
for (int i = 0; i < (1 << k); i++) {
for (int j = 0; j < (1 << k); j++) {
if (weight(codewords[i] & codewords[j]) % 2 != 0) {
printf("FAIL: Code is not self-dual.\n\n");
return;
}
}
}
printf("Verification successful:\n");
printf("All codewords are mutually orthogonal.\n");
printf("Since dim = 4 and n = 8, R(1,3) is self-dual.\n\n");
}
/* --------------------------------------------------
PART C: Weight enumerator of R(2,3)
-------------------------------------------------- */
void solve_part_c() {
printf("--- Part C: Weight Enumerator of R(2,3) ---\n");
int n = 8;
int k = 7;
// Basis: 1, x1, x2, x3, x1x2, x1x3, x2x3
uint8_t basis[7] = {0};
basis[0] = 0xFF;
for (int col = 0; col < n; col++) {
if ((col >> 2) & 1) basis[1] |= (1 << col);
if ((col >> 1) & 1) basis[2] |= (1 << col);
if ((col >> 0) & 1) basis[3] |= (1 << col);
}
basis[4] = basis[1] & basis[2];
basis[5] = basis[1] & basis[3];
basis[6] = basis[2] & basis[3];
int weights[9] = {0};
// Generate all 2^7 = 128 codewords
for (int i = 0; i < (1 << k); i++) {
uint8_t cw = 0;
for (int j = 0; j < k; j++) {
if ((i >> j) & 1) {
cw ^= basis[j];
}
}
weights[weight(cw)]++;
}
// Print weight enumerator
printf("Weight distribution:\n");
for (int w = 0; w <= 8; w++) {
if (weights[w] > 0) {
printf("Weight %d: %d\n", w, weights[w]);
}
}
printf("\nWeight enumerator:\nW(z) = ");
int first = 1;
for (int w = 0; w <= 8; w++) {
if (weights[w] > 0) {
if (!first) printf(" + ");
printf("%dz^%d", weights[w], w);
first = 0;
}
}
printf("\nExpected: W(z) = 1 + 126z^4 + z^8\n\n");
}
int main() {
solve_part_a();
solve_part_b();
solve_part_c();
return 0;
}