## Principles and Analogies of Error Correction Codes

I use a very abstract visual way to explain about different error correction algorithms. Here I will over-simplify every algorithm and then use visualizations instead, just to get the principle of how they works, and why.

Linear Block Code

In linear block code, every codewords will have n-k bits of redundant checkin part, and k-bits of message.

The generator matrix would look like this, where there is some identity matrix in it, that later will be used to generate syndrome to identify errors.

Hamming Code
The picture below shows how to identify error with even parity bits. The bits in black is the message, the bits in green is the parity to make sure that the number of 1 in a circle is even, the bit in red is the error, that later can be identified because the overlapping circle area will show where the error occur.

The Hamming Code works like shown by the table below, the parity bits (unlike the previous method) are inserted in certain positions (2^0, 2^1, 2^2 and 2^3) to make sure that each of every 4 bits of message is being screened so that later the error can be tracked.

Cyclic Code

This is my favorite. This method use the characteristic of polynomial in GF(2^n). So that identifying errors can be done by divide the codeword with the generator g(x). If the result is not 0, there is an error. Another thing that I like from this method is that every codeword is a shift from previous codeword (that’s why this method called “cyclic”) . So the implementation will be very easy, just shifting here and there (using LFSR), which in hardware implementation, is “costless”.

BCH Code

This method is a little bit complicated but the point is, to make a matrix H so that this matrix can screen out every bits (that’s why there are 2 rows that are linearly redundant).

Reed Muller

This one is interesting. This method has orders to identify different number of errors. Look at the matrix below. R(1,3) means that the order is 1 and the message length is 3. In Reed Muller, the pattern is obvious. Each vector in the matrix (x1, x2, x3) are used to search the location of error in convergence. Each row will direct the algorithm to a smaller space of error possibility location.

For R(2, 3), we have the same number bits of message, which is three, but this time in order 2. Means that the matrix will be expanded and thus, more error can be detected. The part of matrix in yellow is the “basic” vectors, while the green shows the “additional” vectors to help allocating more errors.

Now look at R(3,3). More rows of the matrix, and more errors to be detected.

So oversimplifyingly, I can say that error correction code, in principle, how to encode a message (to be a codeword) to get through a channel (error correction code is in domain channel coding, while data compression is in domain source coding) so that we would be able to make the message reliable (while in source coding, the target is not reliability but efficiency), by making sure that we can locate error and fix it. And the way to decode is like the illustration of quadtree below. The methods will generate matrix, or equations, or mathematical characteristic (polynomial groups etc) to help to narrow down the search space.

Hopefully this article can be useful, I will teach Reed Solomon Code next week, and let’s see if I can add up more things here, or publish a new blogpost.

Wah, tanggung Bu, kurang Reed Solomon 😀
Thanks for writing, Bu 🙂

• #### CG 3:08 pm on January 1, 2014 Permalink | Reply

will do when i have time.thx 🙂

## Hello World – Erlang

The easiest way to install Erlang on MacOS is by downloading the .dmg of Erlang here. And then you will get Erlang installed.

And here’s the example of Hello World using Erlang.

## Polynomial Basis Squaring

Finally have successfully found some spare time to do coding to solve this polynomial squaring:

And this is the result, x^5 + x + 1 :

• #### rudi 9:37 pm on May 30, 2013 Permalink | Reply

bu, akan lebih cantik kalo nulis polinomnya pake latex,
$x^5 + x+1$

• #### CG 11:00 am on May 31, 2013 Permalink | Reply

iya belum sempet dirapihin 😀 biasanya saya pake latex for wordpress

## Why Python?

Our research group is developing a library for finite field operations on very long bits, so we start gathering information about the performance of Python on scientific programming, big numbers especially for cryptography.
Here are some important links related to Python for scientific and cryptography implementation:

1. http://www.tutorialspoint.com/python/python_numbers.htm – about Python number representations
2. https://pypi.python.org/pypi/PyECC – a module for implementing Elliptic Curve Cryptography
3. http://theunixgeek.blogspot.com/2008/09/c-vs-python-speed.html – Python compared to C
4. http://www.linuxjournal.com/magazine/use-python-scientific-computing – the use of Python for scientific computing
5. http://scipy-lectures.github.com/ – Python Scientific Lecture Notes
6. http://www.scientificpython.net/ – Scientific Computing with Python
7. http://wiki.python.org/moin/NumericAndScientific – list of modules and tools for various implementation in Python
8. http://ubuntuforums.org/showthread.php?t=1581805 – Python power for large numbers
9. http://programmers.stackexchange.com/questions/128589/how-to-handle-large-numbers – handling big numbers with Python
10. http://www.daniweb.com/software-development/python/threads/364584/very-large-numbers – library for big numbers in Python
11. http://www.daniweb.com/software-development/python/threads/364584/very-large-numbers – Python can handle very big numbers
13. https://gist.github.com/bellbind/1414867 – Elliptic Curve Cryptography implementation in Python

• #### Tafta 5:08 pm on March 16, 2013 Permalink | Reply

The title doesn’t match the content, please dech (pake helm biar ga ditampar)

• #### CG 7:27 pm on March 16, 2013 Permalink | Reply

*tempiling sampe kepalanya lepas*

## Python: Converting String to Binary

A simple code on how to convert string to binary, accessing array string and performing shift operation on binary

``````
#!/usr/bin/python``````

a_str = ‘10110011’
b_str = “00101010”
a_bin = int(a_str, 2)
b_bin = int(b_str, 2)

print “a “, int(a_bin), a_str
print “b “, int(b_bin), b_str
print “a[0] “, a_str[0]
print “b[0:3]”, b_str[0:3]

#print “c “, c, bin(c)[2:]

print “a << 2 “, a_bin << 2, bin(a_bin << 2)[2:]
print “b >> 2 “, b_bin >> 2, bin(b_bin >> 2)[2:]

The result:

• #### tinykuya 3:02 pm on March 15, 2013 Permalink | Reply

ternyata dari string diconvert dulu ke int, terus diconvert lagi ke binary.. ya ya ya.. saya sempat berpikir operasi binernya dalam bentuk array 😀 kalau seperti ini, masuk akal.

terima kasih bu.

• #### CG 3:55 pm on March 15, 2013 Permalink | Reply

sip mudah2an berguna 😉

## Python: Bit Operations

Basic bit operations in Python:

``````
#!/usr/bin/python

a = 60            # 60 = 0011 1100
b = 13            # 13 = 0000 1101
c = 0

print "a = ", (bin(a)[2:]);
print "b = ", (bin(b)[2:]);

c = a & b;        # 12 = 0000 1100
print "a & b = ", (bin(c)[2:]);

c = a | b;        # 61 = 0011 1101
print "a | b = ", (bin(c)[2:]);

c = a ^ b;        # 49 = 0011 0001
print "a ^ b = ", (bin(c)[2:]);

c = ~a;           # -61 = 1100 0011
print "~a = ", (bin(c)[2:]);

c = a << 2;       # 240 = 1111 0000
print "a <> 2;       # 15 = 0000 1111
print "a >> 2 = ", (bin(c)[2:]);
``````

Result:

An interesting link about bit operation algorithm implementation in Python is here.

## Crypto vs Code

Cryptography is the study of mathematical techniques related to aspects of information security such as confidentiality, data integrity, entity authentication, and data origin authentication. [Handbook of Applied Cryptography – Alfred J. Menezes Paul C. van Oorschot Scott A. Vanstone]

Coding is needed for efficient reliable digital transmission and storage. [Error Control Coding – Shu Lin, Daniel J. Costello]. Coding theory is is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, and computer science—for the purpose of designing efficient and reliable data transmission methods. This typically involves the removal of redundancy and the correction (or detection) of errors in the transmitted data. [Wikipedia]

Nggak pakai Alice & Bob?

## 2012 in review

The WordPress.com stats helper monkeys prepared a 2012 annual report for this blog.

Here’s an excerpt:

4,329 films were submitted to the 2012 Cannes Film Festival. This blog had 18,000 views in 2012. If each view were a film, this blog would power 4 Film Festivals

## Resolving Java Heap Space Error

My previous code processed two tables with thousands of rows and had problem with Java Heap Space like shown below:

To overcome this out of memory problem, we should increase the heap size by typing this on command prompt:

And now it works:

## Hello World – Python

I’m learning Python 😀

This is the version of Python I’m using:

And then start using vi to type the code:

The listing of the code:

And run the code:

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r