Error-Correcting codes

For this homework we need to implement a block code for a binary channel, then we need to explain how many errors it is able to detect or correct and why, we need to do a test program and try it out.

So, I do the hamming code because I think is easy to implement and explain, hamming code is a block code that can detect and correct errors in a binary channel, but this code can only detect just one bit for a all the sequence of bits, so for that, you need to implement a variant of this block code, for this homework I just experiment a normal hamming code.

For do the hamming code we need to do some procedures into the program, for example we need to do some subroutine that can do a parity and also check and jump into vector, I'm going to explain how I do it in Python.

So, first of all, we have a sequence of bits, then, I made a subroutine that creates a vector that have a bits only in a position when the number is the power of two, that is in the position 1, 2, 3, 8, 16, 32, 64, etc. and in the others position we didn't want save any data.

Then, we need to compute a bit of parity, so for that, I do a procedure that do a general rule that we have in the hamming code, jump n-1 bits, then check n bits, then jump n bit, etc, at the moment to do that, we have another vector that we need to compute a logic xor for each value in the vector, just for have the parity bits.

Then we need to join the bits of parity into the vector that we have, and we already have a hamming code, but now the important thing is to know when we have an error, so for that we need to do a test of parity, and if we have in each row, 0 in the xor, we are right, it is just the same of the hamming code but in the inverse.

If we can detect an error, we have a sequence of bits that we can translate to a decimal and we have that number to know the position of the error, then just change that bit and we already have a good sequence.

This only works when we have only one bit with an error, but if we have many, we need to implement another error-correcting code, so, in conclusion, this is simple to implement, to understand how works a block code with a correcting solution, but it fail at the moment that we have many errors.

This is an example, suppose that we have the following bits

1010101

Then we do a vector just in the positions that are power of two.

['', '', '1', '', '0', '1', '0', '', '1', '0', '1']

Then we do for each vector, xor of all the items, following the rule " jump n-1 bits, then check n bits..."


['', '', '1', '', '0', '', '0', '', '1', '', '1'] :  1
['', '', '1', '', '', '1', '0', '', '', '0', '1'] :  1
['', '', '', '', '0', '1', '0', '', '', '', '']     :  1
['', '', '', '', '', '', '', '', '1', '0', '1']     :  0


So we add this bit into the coding

['1', '1', '1', '1', '0', '1', '0', '0', '1', '0', '1']

Suppose that we have an error, and we have the next sequence.

['1', '0', '1', '1', '0', '1', '0', '0', '1', '0', '1']

So we do with that sequence, just obtain the bits and compare if we have the same using parity, for that we need to do for each vector an xor.

COMP:1
ERRO:1

COMP:1
ERRO:0

COMP:1
ERRO:1

COMP:0
ERRO:0

We have the next sequence:
['0', '0', '1', '0']
     Pos = 2

Then if we know, in 10 are 2 in decimal, so in the position 2, we have the error.


['1', '0', '1', '1', '0', '1', '0', '0', '1', '0', '1']
['1', '1', '1', '1', '0', '1', '0', '0', '1', '0', '1']

And we correct this sequence.

I hope my english is good and you can understand.

This is my code.

Métodos de diccionario-Byte pair encoding

Para este método se utiliza las repeticiones que sean iguales dentro de una cadena de manera que se sustituyen con variables para al final tener variables como referencia y una cadena más corta, para realizar este ejemplo hice en python una cadena aleatoria de la siguiente manera.

''.join(random.choice("abcde") for x in range(20))

De manera que tengamos una cadena de largo 20 y con un alfabeto A = {a, b, c, d, e}

Esta es la cadena que vamos a utilizar 'bbbeadbaaddadabceacb'

Encontramos los valores que podemos sustituir en la primera iteración

En la primera iteración buscamos caracteres que se repitan pero en bares diferentes por lo que primero voy a comprimir con la variable X a la repetición ea.

• bbbeadbaaddadabceacb
• X = ea

Luego en la segunda iteración encontramos caracteres repetidos como da.

• bbbXdbaaddadabcXcb
• Y = da

Ahora ya no tenemos caracteres diferentes que se repitan, por lo que empezamos a buscar caracteres del mismo tipo que se repitan en la cadena, encontramos bbb

• bbbXdbaadYYbcXcb
• Z = bbb

Encontramos al igual aa en la cuarta iteración.

• ZXdbaadYYbcXcb
• W= aa

Luego encontramos la letra YY repetida

• ZXdbWdYYbcXcb
• Q=YY

Ya no existen patrones de repetición por lo que esta sería nuestra cadena comprimida, junto con su diccionario.

• ZXdbWdQbcXcb
• X = ea
• Y = da
• Z = bbb
• W= aa
• Q=YY

Ahora para decomprimirlo, como ya tenemos el diccionario, en la primera iteración sustituimos la Q ya que esta contiene referencias al mismo diccionario.

• ZXdbWdQbcXcb
• ZXdbWdYYbcXcb

Luego sustituimos la W de la cadena que tenemos

• ZXdbaadYYbcXcb

Ahora, sustituimos la letra Z

• ZXdbaadYYbcXcb
• bbbXdbaadYYbcXcb

Luego, en la siguiente iteración, sustituimos las Y

• bbbXdbaadYYbcXcb
• bbbXdbaaddadabcXcb

Para después en la siguiente iteración y última con la variable X

• bbbXdbaaddadabcXcb
• bbbeadbaaddadabceacb

Entonces como resumen tenemos lo siguiente.

• Cadena = bbbeadbaaddadabceacb   
• largo = 20
• Cadena comprimida = ZXdbWdQbcXcb   
• largo = 12

Huffman adaptativo

Estuve trabajando para hacer el código huffman, lo que hice fue hacer un código que va pasando de 5 en 5 caracteres para ir formando el árbol para al final tener el código huffman, en realidad no se ha implementado el decodificador y en rendimiento no grafique.




No alcancé a graficarlo.

Extra points: Huffman coding

2. Table4.1 gives the relative frequencies,in English prose minus punctuation and blanks, ignoring capitalization, of the alphabetic characters a, b, . . . , z, estimated by examination of a large block of English prose, believed to be typical. This table is copied, with one small change, from [6, Appendix 1]. Find an optimal (with respect to average code word length) prefix-condition encoding scheme for S = {a, b, ... , z} if

(a) A={0,1};
(b) A={0,1,∗}.
(c) What are the lengths of the shortest fixed-length encoding schemes, resulting in uniquely decodable codes, for S, in cases (a) and (b), above?

For do this exercise I made a program that are pretty similar that my last homework where by doing the huffman tree we have the optimal prefix-condition, this is the code.



So we have like result for the question a:

• 'a': '0000', 
• 'c': '010001', 
• 'b': '0111000',
•  'e': '1', 
• 'd': '00011', 
• 'g': '0111011',
•  'f': '001101', 
• 'i': '01101', 
• 'h': '01010', 
• 'k': '00110011', 
• 'j': '0011001011',
•  'm': '001111', 
• 'l': '00010', 
• 'o': '01111',
• 'n': '01100', 
• 'q': '0011001001', 
• 'p': '0111001', 
• 's': '01011',
•  'r': '01001', 
• 'u': '010000', 
• 't': '0010', 
• 'w': '001110',
•  'v': '0011000', 
• 'y': '0111010', 
• 'x': '0011001010', 
• 'z': '0011001000'

Then I modified the code to have another node, so in the alphabet we have a new character and also a new coding data.

• 'a': '11', 
• 'c': '*01',
•  'b': '*0**', 
• 'e': '1'
• 'd': '*11', 
• 'g': '*1**', 
• 'f': '0*0',
•  'i': '01', 
• 'h': '**1', 
• 'k': '*0*1*', 
• 'j': '*0*10', 
• 'm': '0**', 
• 'l': '*10',
•  'o': '10', 
• 'n': '00', 
• 'q': '*0*111', 
• 'p': '*1*0', 
• 's': '***', 
• 'r': '**0', 
• 'u': '*00', 
• 't': '1*', 
• 'w': '0*1', 
• 'v': '*0*0', 
• 'y': '*1*1', 
• 'x': '*0*11*', 
• 'z': '*0*110'

For the next question we have that e are the last in the list and only have a number 1 as a bit of codification and for the question b also have e with one bit, but in general we have a code more shorter in the second one than in the first one.

Huffman coding

For this week we need to implement the tree-based Huffman coding for Unicode strings, implementing the tree structure, then we need to do a report with a design of an experiment to determine the worst-case and typical-case complexity and compression ratio.

Determining the worst-case and typical-case

As we know, fibonacci sequence are the sum of the previous two, knowing at first that Fo = 0 and F1 = 1, this sequence produces a tree that are the most unbalanced, because if we know that huffman are base in the last two frequencies which produce another node that are the sum of both, so, if we have a fibonacci sequence as a frequency of the letters that we would like to test, we can have this type of tree.

For example, let say that we have these case, when we have only 7 letter, just for know how works.


1, 1, 2, 3
a, b, cc, ddd


Alphabet and probability:
a : 0.142857 = 1/7
b : 0.142857 = 1/7
c : 0.285714 = 2/7
d : 0.428571 = 3/7

Tree:

                  [1] d
[] cabd
                                 [1] b
                      [1] ab
                                 [0] a
           [0] cab
                      [0] c

The same:

              cabd

             /        \
           d        cab
                     /    \
                    c   ab
                        /  \   
                        a  b

We can see that the tree have only new nodes just for one side, because we made the tree having the sum of the probabilities of frequency, and have a pattern that builds the tree in that way, also we can say that if the have in all the probabilities the same number, would have the same pattern.

A typical case is when we have a frequencies that are not the same for all the text or that don't have the pattern of fibonacci, so I made an experiment for the type that I think is interesting, I made a different graphics that can shows that these type of cases are bad compare to the average case.

We have in this graphic the sum of bits that need to handle with a entire alphabet, using ascii, without compress the bits in the line yellow, the average using huffman compression and then using fibonacci sequence frequency and compression with huffman, with a sample of 35 strings with different size.

In this graphic, we can see the compress ratio between the average-case and the worst-case, we can see that clearly are much difference between them, having a difference about 62% more compress than the strings that have a fibonacci sequence.

Program

Assignment 2: Experiment for KMP & BM

For homework in the subject Information Theory, we need to do un experiment to check how is the performance between different algorithms that can search in a text, different patterns.

For do this experiment I made both algorithms in Python, then I put a sub procedure that repeat 30 times, change the value for how long are the pattern, the text and the amount of letters that we use to choose for have different prospective about how the algorithm works, it is important to know that for do the patters I use a function that do string random and also create a pattern randomly.

First at all, the following image you can see a map color where we can find 3 different values plotted, how long is the pattern, how long is the text that we check with the pattern and, finally I put a variable that checks the time that the computer wait for do the search, then when the algorithm finish I return this value and I used for have an estimation with the time.

In this image, you can see that if we have a pattern that are just for 1 to 4 letters, we have an algorithm that can do the search and in a time (that is plot in color) and there is a point that have the color almost red, which means that we have problems with the time to do the search of the pattern, but is just in some search, because in the following map of the next algorithm BM, we have more stress but down for the medium.

In this other map, we have that there is not stress as the another algorithm, because we do not have points where the time are up of the medium, but we have more points in purple, which means that we have a lot stress and up for medium.

This is another test, when we can see that BM algorithm is more purple, so, takes more time to search the words.

This is the code:

Plot in gnuplot

Assignment 1: Noisy channel

For this homework we need to do a simulation of a noisy channel where we have a binary input alphabet with probabilities that can handle the success or fail to pass a word that we would like to transmit.


For do this experiment I use a combination between:

• Python that took for parameters:
• Size of the word
• frequency of succeed
• Probability for one that can transmit
• Probability for zero that can transmit  
• Times that we want to do an experiment.

• In a Bash do:
• Change the frequency of succeed
• Change Probability for one and zero
• Call to the python script to change those variables

• In AWK I can:
• Obtain a mean and also an standard deviation.

Then we use gnuplot to interpret the data that we obtain, so in the following plot I will explain about who a noisy channel works and how all the data that we use in the experiment are connected each other and made that a channel fail or success in transmit binary data.

This is a graphic that I generated for demonstrate that, when I augmented the size of the binary word, the success for transmit is  almost nothing, both if we have a word for example 2**0, the test only send 1 bit, so we have a many chances that this bit can transmit.

Also, this is another graphic that we can see that, when we have a large word we have a 0 probability to send the word correctly, so we can view the circle in black express the standard deviation that we can compute in the AWK script.

This are the same graphics but separated between the probability success 1 and 0.

We can notice that, when we have more frequency of zeros and more probability of success of 1, the probability of zeros is poor, so the standard deviation is going to down, that is because the word transmit more 1 than 0.

Code.

Python

Bash

GNUPLOT

AWK

This is my GitHub.

Information theory and coding methods

Information theory and coding methods