HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaModerate

Calculating the minimum distance of a linear code

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
linearthedistanceminimumcalculatingcode

Problem

This is a solution for the problem named Codes on the kattis platform:


Given a generator matrix of a linear code, calculate the minimum distance of the code.

I'm looking for reviews on optimization and best practices. Code readability should be preserved.

public static class LinearCode {
   private int[][] generator;
   private int n;
   private int k;

   public LinearCode(int[][] generator, int n, int k) {
      this.generator = generator;
      this.n = n;
      this.k = k;
   }

   public int getMinimumDistance() {
      int minDistance = n;
      int maxKString = 1 >> z) & 1;
                  p = (p + a * b) & 1;
              }
              // distance as number if 1 bits
              distance += p;
          }

          minDistance = Math.min(minDistance, distance);
      }

      return minDistance;
   }
}

Solution

The n and k parameters seem pointless: you can derive them from the dimensions of the received generator matrix:

int n = generator.length;
int k = generator[0].length;


Instead of this:

for (int j = 0; j < n; j++) {


You could replace using for-each, which is just more natural:

for (int[] row : generator) {


I don't really see a reason to store the parameters as fields.
The class doesn't need to hold data.
You need just a pure function,
so this can be a public static method.

Putting it together

Applying the above suggestions (+ a few minor things):

public static int getMinimumDistance(int[][] generator) {
    int n = generator.length;
    int k = generator[0].length;
    int minDistance = n;
    int maxKString = 1 >> z) & 1;
                p = (p + a * b) & 1;
            }
            // distance as number if 1 bits
            distance += p;
        }

        minDistance = Math.min(minDistance, distance);
    }

    return minDistance;
}


Unit testing

I recommend adding unit tests to verify your solution, for example:

@Test
public void testSampleExercise1() {
    assertEquals(3, LinearCode.getMinimumDistance(new int[][]{
            {1, 0, 0, 0},
            {0, 1, 0, 0},
            {0, 0, 1, 0},
            {0, 0, 0, 1},
            {0, 1, 1, 1},
            {1, 0, 1, 1},
            {1, 1, 0, 1},
    }));
}

@Test
public void testSampleExercise2() {
    assertEquals(0, LinearCode.getMinimumDistance(new int[][]{
            {1, 1},
            {0, 0},
            {1, 1},
    }));
}

Code Snippets

int n = generator.length;
int k = generator[0].length;
for (int j = 0; j < n; j++) {
for (int[] row : generator) {
public static int getMinimumDistance(int[][] generator) {
    int n = generator.length;
    int k = generator[0].length;
    int minDistance = n;
    int maxKString = 1 << k;

    // generate all k-strings
    for (int i = 1; i < maxKString; i++) {
        int distance = 0;

        // matrix multiplication
        for (int[] row : generator) {
            int p = 0;
            for (int z = 0; z < k; z++) {
                int a = row[k - z - 1];
                int b = (i >>> z) & 1;
                p = (p + a * b) & 1;
            }
            // distance as number if 1 bits
            distance += p;
        }

        minDistance = Math.min(minDistance, distance);
    }

    return minDistance;
}
@Test
public void testSampleExercise1() {
    assertEquals(3, LinearCode.getMinimumDistance(new int[][]{
            {1, 0, 0, 0},
            {0, 1, 0, 0},
            {0, 0, 1, 0},
            {0, 0, 0, 1},
            {0, 1, 1, 1},
            {1, 0, 1, 1},
            {1, 1, 0, 1},
    }));
}

@Test
public void testSampleExercise2() {
    assertEquals(0, LinearCode.getMinimumDistance(new int[][]{
            {1, 1},
            {0, 0},
            {1, 1},
    }));
}

Context

StackExchange Code Review Q#67249, answer score: 11

Revisions (0)

No revisions yet.