Hamming Error Correction with Kotlin – part 2

In this article, we continue where we left off and focus solely on error detection for Hamming codes.

https://touk.pl/blog/2017/10/17/hamming-error-correction-with-kotlin-part-1/

Error Correction

Utilizing Hamming(7,4) encoding allows us to detect double-bit errors and even correct single-bit ones!

During the encoding, we only add parity bits, so the happy path decoding scenario involves stripping the message from the parity bits which reside at known indexes (1,2,4…n, 2n):

fun stripHammingMetadata(input: EncodedString): BinaryString {
    return input.value.asSequence()
      .filterIndexed { i, _ -> (i + 1).isPowerOfTwo().not() }
      .joinToString("")
      .let(::BinaryString)
}

This is rarely the case because since we made effort to calculate parity bits, we want to leverage them first.

The codeword validation is quite intuitive if you already understand the encoding process. We simply need to recalculate all parity bits and do the parity check (check if those values match what’s in the message):

private fun indexesOfInvalidParityBits(input: EncodedString): List<Int> {
    fun toValidationResult(it: Int, input: EncodedString): Pair<Int, Boolean> =
      helper.parityIndicesSequence(it - 1, input.length)
        .map { v -> input[v].toBinaryInt() }
        .fold(input[it - 1].toBinaryInt()) { a, b -> a xor b }
        .let { r -> it to (r == 0) }

    return generateSequence(1) { it * 2 }
      .takeWhile { it < input.length }
      .map { toValidationResult(it, input) }
      .filter { !it.second }
      .map { it.first }
      .toList()
}

If they all match, then the codeword does not contain any errors:

override fun isValid(codeWord: EncodedString) =
  indexesOfInvalidParityBits(input).isEmpty()

Now, when we already know if the message was transmitted incorrectly, we can request the sender to retransmit the message… or try to correct it ourselves.

Finding the distorted bit is as easy as summing the indexes of invalid parity bits – the result is the index of the faulty one. In order to correct the message, we can simply flip the bit:

override fun decode(codeWord: EncodedString): BinaryString =
  indexesOfInvalidParityBits(codeWord).let { result ->
      when (result.isEmpty()) {
          true -> codeWord
          false -> codeWord.withBitFlippedAt(result.sum() - 1)
      }.let { extractor.stripHammingMetadata(it) }
  }

We flip the bit using an extension:

private fun EncodedString.withBitFlippedAt(index: Int) = this[index].toString().toInt()
  .let { this.value.replaceRange(index, index + 1, ((it + 1) % 2).toString()) }
  .let(::EncodedString)

We can see that it works by writing a home-made property test:

@Test
fun shouldEncodeAndDecodeWithSingleBitErrors() = repeat(10000) {
    randomMessage().let {
        assertThat(it).isEqualTo(decoder.decode(encoder.encode(it)
          .withBitFlippedAt(rand.nextInt(it.length))))
    }
}

Unfortunately, the Hamming (7,4) does not distinguish between codewords containing one or two distorted bits. If you try to correct the two-bit error, the result will be incorrect.

Disappointing, right? This is what drove the decision to make use of an additional parity bit and create the Hamming (8,4).

Conclusion

We’ve seen how the error correction for Hamming codes look like and went through the extensive off-by-one-error workout.

Code snippets can be found on GitHub.

You May Also Like

Thought static method can’t be easy to mock, stub nor track? Wrong!

No matter why, no matter is it a good idea. Sometimes one just wants to check or it's necessary to be done. Mock a static method, woot? Impossibru!

In pure Java world it is still a struggle. But Groovy allows you to do that really simple. Well, not groovy alone, but with a great support of Spock.

Lets move on straight to the example. To catch some context we have an abstract for the example needs. A marketing project with a set of offers. One to many.

import spock.lang.Specification

class OfferFacadeSpec extends Specification {

    OfferFacade facade = new OfferFacade()

    def setup() {
        GroovyMock(Project, global: true)
    }

    def 'delegates an add offer call to the domain with proper params'() {
        given:
            Map params = [projId: projectId, name: offerName]

        when:
            Offer returnedOffer = facade.add(params)

        then:
            1 * Project.addOffer(projectId, _) >> { projId, offer -> offer }
            returnedOffer.name == params.name

        where:
            projectId | offerName
            1         | 'an Offer'
            15        | 'whasup!?'
            123       | 'doskonała oferta - kup teraz!'
    }
}
So we test a facade responsible for handling "add offer to the project" call triggered  somewhere in a GUI.
We want to ensure that static method Project.addOffer(long, Offer) will receive correct params when java.util.Map with user form input comes to the facade.add(params).
This is unit test, so how Project.addOffer() works is out of scope. Thus we want to stub it.

The most important is a GroovyMock(Project, global: true) statement.
What it does is modifing Project class to behave like a Spock's mock. 
GroovyMock() itself is a method inherited from SpecificationThe global flag is necessary to enable mocking static methods.
However when one comes to the need of mocking static method, author of Spock Framework advice to consider redesigning of implementation. It's not a bad advice, I must say.

Another important thing are assertions at then: block. First one checks an interaction, if the Project.addOffer() method was called exactly once, with a 1st argument equal to the projectId and some other param (we don't have an object instance yet to assert anything about it).
Right shit operator leads us to the stub which replaces original method implementation by such statement.
As a good stub it does nothing. The original method definition has return type Offer. The stub needs to do the same. So an offer passed as the 2nd argument is just returned.
Thanks to this we can assert about name property if it's equal with the value from params. If no return was designed the name could be checked inside the stub Closure, prefixed with an assert keyword.

Worth of  mentioning is that if you want to track interactions of original static method implementation without replacing it, then you should try using GroovySpy instead of GroovyMock.

Unfortunately static methods declared at Java object can't be treated in such ways. Though regular mocks and whole goodness of Spock can be used to test pure Java code, which is awesome anyway :)No matter why, no matter is it a good idea. Sometimes one just wants to check or it's necessary to be done. Mock a static method, woot? Impossibru!

In pure Java world it is still a struggle. But Groovy allows you to do that really simple. Well, not groovy alone, but with a great support of Spock.

Lets move on straight to the example. To catch some context we have an abstract for the example needs. A marketing project with a set of offers. One to many.

import spock.lang.Specification

class OfferFacadeSpec extends Specification {

    OfferFacade facade = new OfferFacade()

    def setup() {
        GroovyMock(Project, global: true)
    }

    def 'delegates an add offer call to the domain with proper params'() {
        given:
            Map params = [projId: projectId, name: offerName]

        when:
            Offer returnedOffer = facade.add(params)

        then:
            1 * Project.addOffer(projectId, _) >> { projId, offer -> offer }
            returnedOffer.name == params.name

        where:
            projectId | offerName
            1         | 'an Offer'
            15        | 'whasup!?'
            123       | 'doskonała oferta - kup teraz!'
    }
}
So we test a facade responsible for handling "add offer to the project" call triggered  somewhere in a GUI.
We want to ensure that static method Project.addOffer(long, Offer) will receive correct params when java.util.Map with user form input comes to the facade.add(params).
This is unit test, so how Project.addOffer() works is out of scope. Thus we want to stub it.

The most important is a GroovyMock(Project, global: true) statement.
What it does is modifing Project class to behave like a Spock's mock. 
GroovyMock() itself is a method inherited from SpecificationThe global flag is necessary to enable mocking static methods.
However when one comes to the need of mocking static method, author of Spock Framework advice to consider redesigning of implementation. It's not a bad advice, I must say.

Another important thing are assertions at then: block. First one checks an interaction, if the Project.addOffer() method was called exactly once, with a 1st argument equal to the projectId and some other param (we don't have an object instance yet to assert anything about it).
Right shit operator leads us to the stub which replaces original method implementation by such statement.
As a good stub it does nothing. The original method definition has return type Offer. The stub needs to do the same. So an offer passed as the 2nd argument is just returned.
Thanks to this we can assert about name property if it's equal with the value from params. If no return was designed the name could be checked inside the stub Closure, prefixed with an assert keyword.

Worth of  mentioning is that if you want to track interactions of original static method implementation without replacing it, then you should try using GroovySpy instead of GroovyMock.

Unfortunately static methods declared at Java object can't be treated in such ways. Though regular mocks and whole goodness of Spock can be used to test pure Java code, which is awesome anyway :)

Tomcat: Problemy z requestami zawierającymi polskie znaki diakrytyczne


Jeśli jest problem z pobieraniem plików z polskimi znakami diakrytycznymi, to trzeba dopisać kodowanie do connectora w tomcat/conf/server.xml

URIEncoding="UTF-8"

Typowa konfiguracja connectora będzie wyglądała tak

<Connector port="8080" protocol="HTTP/1.1"
               connectionTimeout="20000"
               redirectPort="8443" URIEncoding="UTF-8" />