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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from random import randint, choice, random | |
| def main(): | |
| bits = "1010101" | |
| code = hamming_code(bits) | |
| print("Codigo hamming :"+str(code)) | |
| code_error = hamming_code(bits) | |
| code_error_nuevo = genera_error(code_error, 1) | |
| comparar, xor = prueba_paridad(code_error_nuevo) | |
| print("Codigo error:"+str(code_error_nuevo)) | |
| print("Codigo prueba:"+str(comparar)) | |
| tam = [] | |
| if code_error != comparar: | |
| print("Encontrando error y reparando. . . ") | |
| Pos = 1 | |
| tam = 0 | |
| Error_Pos = [] | |
| while True: | |
| if tam == len(code_error): | |
| break | |
| if ((Pos & (Pos - 1)) == 0) and Pos != 0: | |
| print("Bit comprueba:" + str(comparar[tam])) | |
| print("Bit codigo erro:" + str(code_error_nuevo[tam])) | |
| comp = int(comparar[tam]) ^ int(code_error_nuevo[tam]) | |
| print("xor:" + str(comp)) | |
| Error_Pos.append(str(comp)) | |
| print(" ") | |
| tam = tam + 1 | |
| Pos = Pos + 1 | |
| otro = pos(Error_Pos) | |
| print(otro) | |
| print("Actualizo . . ") | |
| if code_error[otro-1] == "0": | |
| code_error[otro-1] = "1" | |
| else: | |
| code_error[otro-1] = "0" | |
| print(code_error) | |
| #Hace hamming code | |
| def hamming_code(bits): | |
| datos = crear_datos(bits) | |
| print datos | |
| for i in range(len(datos)): | |
| Pos = i + 1 | |
| if ((Pos & (Pos - 1)) == 0) and Pos != 0: | |
| P, d = salta_cmp(datos, i+1) | |
| xor = xor_lista(d) | |
| print(str(P) + str(":") + str(xor)) | |
| datos[i] = str(xor) | |
| return datos | |
| #Saca el xor de todo el vector | |
| def xor_lista(d): | |
| i = 0 | |
| xor = int(d[i]) ^ int(d[i+1]) | |
| while True: | |
| i = i + 1 | |
| if i < len(d)-1: | |
| xor = xor ^ int(d[i+1]) | |
| else: | |
| return xor | |
| #Genera la regla salta y comprueba | |
| def salta_cmp(datos, pos): | |
| paridad = [] | |
| for i in range(len(datos)): | |
| paridad.append("") | |
| salta = pos - 1 | |
| cmp = pos | |
| Pos = 0 | |
| d = [] | |
| while True: | |
| for i in range(salta): | |
| if Pos == len(datos): | |
| d.pop(0) | |
| return paridad, d | |
| paridad[Pos] = "" | |
| Pos = Pos + 1 | |
| for i in range(cmp): | |
| if Pos == len(datos): | |
| d.pop(0) | |
| return paridad, d | |
| paridad[Pos] = datos[Pos] | |
| d.append(datos[Pos]) | |
| Pos = Pos + 1 | |
| salta = pos | |
| cmp = pos | |
| #Produce un error | |
| def genera_error(code_error, cuantos): | |
| for i in range(cuantos): | |
| Pos = randint(0, len(code_error)-1) | |
| if int(code_error[Pos]) == 0: | |
| code_error[Pos] = "1" | |
| else: | |
| code_error[Pos] = "0" | |
| return code_error | |
| #Prueba de paridad a codigo | |
| def prueba_paridad(code): | |
| print(str("PP:")+str(code)) | |
| datos = extraer_datos(code) | |
| xors = [] | |
| for i in range(len(datos)): | |
| Pos = i + 1 | |
| if ((Pos & (Pos - 1)) == 0) and Pos != 0: | |
| P, d = salta_cmp(datos, i+1) | |
| xor = xor_lista(d) | |
| datos[i] = str(xor) | |
| print(str(P) + str(":") + str(xor)) | |
| xors.append(str(xor)) | |
| return datos, xors | |
| #Obtener los bits cuando tenemos un codigo hamming | |
| def extraer_datos(code): | |
| datos = [] | |
| Pos = 1 | |
| tam = 0 | |
| while True: | |
| if tam == len(code): | |
| return datos | |
| if ((Pos & (Pos - 1)) == 0) and Pos != 0: | |
| datos.append("") | |
| tam = tam + 1 | |
| else: | |
| datos.append(code[tam]) | |
| tam = tam + 1 | |
| Pos = Pos + 1 | |
| #Crear vector cuando solamente tenemos bits | |
| def crear_datos(bits): | |
| datos = [] | |
| Pos = 1 | |
| tam = 0 | |
| while True: | |
| if tam == len(bits): | |
| return datos | |
| if ((Pos & (Pos - 1)) == 0) and Pos != 0: | |
| datos.append("") | |
| else: | |
| datos.append(bits[tam]) | |
| tam = tam + 1 | |
| Pos = Pos + 1 | |
| #Regresa posicion de error | |
| def pos(array): | |
| val = 0 | |
| for i in range(len(array)): | |
| if array[i] == "1": | |
| val = val + 2**i | |
| return val | |
| #Experimento NO TERMINADO | |
| def experimento(): | |
| err = 0 | |
| bien = 0 | |
| for i in range(1000): | |
| bits = "".join(choice(["0","1"]) for x in range(i)) | |
| if random() > 0.3: | |
| code = hamming_code(bits) | |
| code_error = hamming_code(bits) | |
| code_error_nuevo = genera_error(code_error, choice([0,1])) | |
| comparar, xor = prueba_paridad(code_error_nuevo) | |
| if code_error != comparar: | |
| err = 1 | |
| bien = 0 | |
| else: | |
| err = 0 | |
| bien = 1 | |
| Pos = 1 | |
| tam = 0 | |
| Error_Pos = [] | |
| while True: | |
| if tam == len(code_error): | |
| break | |
| if ((Pos & (Pos - 1)) == 0) and Pos != 0: | |
| comp = int(comparar[tam]) ^ int(code_error_nuevo[tam]) | |
| Error_Pos.append(str(comp)) | |
| tam = tam + 1 | |
| Pos = Pos + 1 | |
| try: | |
| otro = pos(Error_Pos) | |
| if otro <= len(code): | |
| if code_error[otro-1] == "0": | |
| code_error[otro-1] = "1" | |
| else: | |
| code_error[otro-1] = "0" | |
| except: | |
| code_error_nuevo = code_error | |
| if code_error == code: | |
| arregla = 1 | |
| else: | |
| arregla = 0 | |
| else: | |
| code = hamming_code(bits) | |
| arregla = 0 | |
| bien = 1 | |
| mal = 0 | |
| arregla = 1 | |
| print str(i) + str(bien) + str(mal) + str(arregla) | |
| main() |
Pues, casi lo llevas. 4+3.
ResponderEliminar