Hamming Error Correction With Java and Vavr (Part 3)

Since there was some interest in seeing hamming encoders and decoders implemented in Java, in this article, we’ll take a look at how we can implement the same hamming encoder/decoder using Java and the Vavr library.

Previous articles from the series:

Hamming Error Correction with Kotlin – part 1

Hamming Error Correction with Kotlin – part 2

Encoder

package com.pivovarit.hamming.vavr;

import static io.vavr.API.$;
import static io.vavr.API.Case;
import static io.vavr.API.Match;

class VavrHammingEncoder implements HammingEncoder {

    private final HammingHelper helper = new HammingHelper();

    @Override
    public EncodedString encode(BinaryString input) {
        String result = helper.getHammingCodewordIndices(input.getValue().length())
          .map(i -> toHammingCodeValue(i, input))
          .reduce(String::concat);

        return EncodedString.of(result);
    }

    private String toHammingCodeValue(int it, BinaryString input) {
        return Match(it + 1).of(
          Case($(HammingHelper::isPowerOfTwo), () -> helper.getParityBit(it, input)),
          Case($(), () -> helper.getDataBit(it, input))
        );
    }
}

Decoder

package com.pivovarit.hamming.vavr;

import io.vavr.collection.List;
import io.vavr.collection.Stream;

import static io.vavr.API.$;
import static io.vavr.API.Case;
import static io.vavr.API.Match;

class VavrHammingDecoder implements HammingDecoder {

    private final HammingHelper helper = new HammingHelper();
    private final HammingMessageExtractor extractor = new HammingMessageExtractor();

    @Override
    public boolean isValid(EncodedString input) {
        return indexesOfInvalidParityBits(input).isEmpty();
    }

    @Override
    public BinaryString decode(EncodedString input) {
        EncodedString corrected = Match(indexesOfInvalidParityBits(input).isEmpty()).of(
          Case($(true), () -> input),
          Case($(false), () -> withBitFlippedAt(input, indexesOfInvalidParityBits(input).reduce((a, b) -> a + b) - 1))
        );

        return extractor.stripHammingMetadata(corrected);
    }

    private List<Integer> indexesOfInvalidParityBits(EncodedString input) {
        return Stream.iterate(1, i -> i * 2)
          .takeWhile(it -> it < input.getValue().length())
          .filter(it -> helper.parityIndicesSequence(it - 1, input.getValue().length())
            .map(v -> toBinaryInt(input, v))
            .fold(toBinaryInt(input, it - 1), (a, b) -> a ^ b) != 0)
          .toList();
    }

    private Integer toBinaryInt(EncodedString input, Integer v) {
        return Integer.valueOf(Character.toString(input.getValue().charAt(v)));
    }

    private EncodedString withBitFlippedAt(EncodedString source, int ind) {
        char it = source.getValue().charAt(ind);
        StringBuilder builder = new StringBuilder(source.getValue());
        builder.setCharAt(ind, it == '0' ? '1' : '0');
        return EncodedString.of(builder.toString());
    }
}

HammingMessageExtractor

package com.pivovarit.hamming.vavr;

import io.vavr.Tuple;
import io.vavr.collection.Stream;

class HammingMessageExtractor {
    BinaryString stripHammingMetadata(EncodedString input) {
        String raw = Stream.from(0, 1).take(input.getValue().length())
          .map(i -> Tuple.of(i + 1, Character.toString(input.getValue().charAt(i))))
          .filter(t -> !HammingHelper.isPowerOfTwo(t._1))
          .map(i -> i._2)
          .foldLeft("", String::concat);

        return BinaryString.of(raw);
    }
}

HammingHelper

package com.pivovarit.hamming.vavr;

import io.vavr.collection.Stream;

class HammingHelper {

    static boolean isPowerOfTwo(int i) {
        return (i & -i) == i;
    }

    int codewordSize(int msgLength) {
        return Stream.from(2, 1)
          .filter(r -> msgLength + r + 1 <= 1 << r)
          .map(r -> r + msgLength)
          .head();
    }

    Stream<Integer> getHammingCodewordIndices(int msgLength) {
        return Stream.from(0, 1)
          .take(codewordSize(msgLength));
    }

    String getParityBit(int codeWordIndex, BinaryString msg) {
        return parityIndicesSequence(codeWordIndex, codewordSize(msg.getValue().length()))
          .map(it -> getDataBit(it, msg))
          .map(Integer::valueOf)
          .reduce((a, b) -> (a + b) % 2)
          .toString();
    }

    String getDataBit(int ind, BinaryString input) {
        return Character.toString(
          input.getValue().charAt(ind - Integer.toBinaryString(ind).length()));
    }

    Stream<Integer> parityIndicesSequence(int startIndex, int endExclusive) {
        return Stream.from(startIndex, 1)
          .take(endExclusive - startIndex)
          .zipWithIndex()
          .filter(t -> (t._2 % ((2 * (startIndex + 1)))) < startIndex + 1)
          .map(t -> t._1)
          .drop(1);
    }
}

Sources

A complete example can be found on GitHub.