DZone
Java Zone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
  • Refcardz
  • Trend Reports
  • Webinars
  • Zones
  • |
    • Agile
    • AI
    • Big Data
    • Cloud
    • Database
    • DevOps
    • Integration
    • IoT
    • Java
    • Microservices
    • Open Source
    • Performance
    • Security
    • Web Dev
DZone > Java Zone > Hamming Error Correction With Kotlin (Part 2)

Hamming Error Correction With Kotlin (Part 2)

Diving more deeply into Hamming(7,4) encoding, we tackle error detection and correction, off-by-one-error workouts, and the challeges of the (7,4) method.

Grzegorz Piwowarek user avatar by
Grzegorz Piwowarek
·
Oct. 26, 17 · Java Zone · Tutorial
Like (4)
Save
Tweet
5.91K Views

Join the DZone community and get the full member experience.

Join For Free

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

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 of 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 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 homemade property test:

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


Unfortunately, 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.

Kotlin (programming language) Snippet (programming) Leverage (statistics) Testing GitHub Property (programming) Requests

Published at DZone with permission of Grzegorz Piwowarek, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • 6 Best Books to Learn Multithreading and Concurrency in Java
  • Why I'm Choosing Pulumi Over Terraform
  • 10 Books Every Senior Engineer Should Read
  • Modern REST API Design Principles and Rules

Comments

Java Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • MVB Program
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends:

DZone.com is powered by 

AnswerHub logo