Hamming Error Correction With Java and Vavr (Part 3)
Want to take a look at using hamming encoders and decoders in Java? Check out this post to get the code using hamming encoders and decoders with the Vavr library.
Join the DZone community and get the full member experience.
Join For FreeSince 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:
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.
Java (programming language)
Published at DZone with permission of Grzegorz Piwowarek, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
Trending
-
Java Concurrency: Condition
-
How to Implement Istio in Multicloud and Multicluster
-
Tactics and Strategies on Software Development: How To Reach Successful Software [Video]
-
Top Six React Development Tools
Comments