Коды хемминга в питоне

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Implementation of Hamming Code in Python, developed for Computer Networks class.

License

LeonardoBringel/HammingCode

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Developed by Richard W. Hamming, the Hamming Code is used to detect and correct errors that may occur when data is moved from the sender to the reciever.

The way that Hamming Code ensures that no bits were lost during the data transfer is by generating and adding Parity Bits.

Those bits are placed at certain positions that cover an array of the data bits. The position is determined by the power of 2 (1, 2, 4, 8. ).

(e.g.) determining the position of the parity bits for: "1 0 1 1" "_ _ 1 _ 0 1 1" (bits 1, 2, 4) 

The Parity Bit is determined by the sum of the checked bits. The Parity Bit is 0 if the sum result is an even number, otherwise it is 1.

The position of the Parity Bit determines the sequence of bits that it alternatively checks and skips.

(e.g.) following our same example: "_ _ 1 _ 0 1 1" parity 1 (bit 1) = starting by itself, checks 1 bit, skips 1, and so on parity 2 (bit 2) = starting by itself, checks 2 bits, skips 2, and so on parity 3 (bit 4) = starting by itself, checks 4 bits, skips 4, and so on parity 1 = 0 + 1 + 0 + 1 = 2 (even) parity 2 = 0 + 1 + 1 + 1 = 3 (odd) parity 3 = 0 + 0 + 1 + 1 = 2 (even) hamming code: "0 1 1 0 0 1 1" 

Note: The parity itself assumes value 0 when being calculated.

The way that the receiver will decode the word is very similar to the way of the sender’s encoding.

The first thing to do is to locate the parity bits and recalculate them, comparing the result with the received word.

(e.g.) received word: "0 1 1 0 1 1 1" recalculating parity: parity 1 (bit 1) = 3 (odd) = 1 parity 2 (bit 2) = 3 (odd) = 1 parity 3 (bit 4) = 3 (odd) = 1 

If any difference is found, it means that our data has been corrupted. To locate the corrupted bit, simply sum the position of the parity bits that are different from the received and the result will be the position of the corrupted bit.

(e.g.) received word: "0 1 1 0 1 1 1", calculated word: "1 1 1 1 1 1 1" location = 1 + 4 = 5 inverting bit 5 in the received word: "0 1 1 0 0 1 1" 

After correcting the bit, we can recalculate to ensure that the data is no longer corrupted and then remove the parity bits.

(e.g.) received word: "0 1 1 0 0 1 1" original word: "1 0 1 1" 

This project is MIT licensed, as found in the LICENSE file.

About

Implementation of Hamming Code in Python, developed for Computer Networks class.

Источник

vilisov / hamming_code.py

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

import random

# длина блока кодирования

CHUNK_LENGTH = 8

# проверка длины блока

assert not CHUNK_LENGTH % 8 , ‘Длина блока должна быть кратна 8’

# вычисление контрольных бит

CHECK_BITS = [ i for i in range ( 1 , CHUNK_LENGTH + 1 ) if not i & ( i — 1 )]

def chars_to_bin ( chars ):

«»»

Преобразование символов в бинарный формат

«»»

assert not len ( chars ) * 8 % CHUNK_LENGTH , ‘Длина кодируемых данных должна быть кратна длине блока кодирования’

return » . join ([ bin ( ord ( c ))[ 2 :]. zfill ( 8 ) for c in chars ])

def chunk_iterator ( text_bin , chunk_size = CHUNK_LENGTH ):

«»»

Поблочный вывод бинарных данных

«»»

for i in range ( len ( text_bin )):

if not i % chunk_size :

yield text_bin [ i : i + chunk_size ]

def get_check_bits_data ( value_bin ):

«»»

Получение информации о контрольных битах из бинарного блока данных

«»»

check_bits_count_map =

for index , value in enumerate ( value_bin , 1 ):

if int ( value ):

bin_char_list = list ( bin ( index )[ 2 :]. zfill ( 8 ))

bin_char_list . reverse ()

for degree in [ 2 ** int ( i ) for i , value in enumerate ( bin_char_list ) if int ( value )]:

check_bits_count_map [ degree ] += 1

check_bits_value_map = <>

for check_bit , count in check_bits_count_map . items ():

check_bits_value_map [ check_bit ] = 0 if not count % 2 else 1

return check_bits_value_map

def set_empty_check_bits ( value_bin ):

«»»

Добавить в бинарный блок «пустые» контрольные биты

«»»

for bit in CHECK_BITS :

value_bin = value_bin [: bit — 1 ] + ‘0’ + value_bin [ bit — 1 :]

return value_bin

def set_check_bits ( value_bin ):

«»»

Установить значения контрольных бит

«»»

value_bin = set_empty_check_bits ( value_bin )

check_bits_data = get_check_bits_data ( value_bin )

for check_bit , bit_value in check_bits_data . items ():

value_bin = » . format (

value_bin [: check_bit — 1 ], bit_value , value_bin [ check_bit :])

return value_bin

def get_check_bits ( value_bin ):

«»»

Получить информацию о контрольных битах из блока бинарных данных

«»»

check_bits = <>

for index , value in enumerate ( value_bin , 1 ):

if index in CHECK_BITS :

check_bits [ index ] = int ( value )

return check_bits

def exclude_check_bits ( value_bin ):

«»»

Исключить информацию о контрольных битах из блока бинарных данных

«»»

clean_value_bin = »

for index , char_bin in enumerate ( list ( value_bin ), 1 ):

if index not in CHECK_BITS :

clean_value_bin += char_bin

return clean_value_bin

def set_errors ( encoded ):

«»»

Допустить ошибку в блоках бинарных данных

«»»

result = »

for chunk in chunk_iterator ( encoded , CHUNK_LENGTH + len ( CHECK_BITS )):

num_bit = random . randint ( 1 , len ( chunk ))

chunk = » . format ( chunk [: num_bit — 1 ], int ( chunk [ num_bit — 1 ]) ^ 1 , chunk [ num_bit :])

result += ( chunk )

return result

def check_and_fix_error ( encoded_chunk ):

«»»

Проверка и исправление ошибки в блоке бинарных данных

«»»

check_bits_encoded = get_check_bits ( encoded_chunk )

check_item = exclude_check_bits ( encoded_chunk )

check_item = set_check_bits ( check_item )

check_bits = get_check_bits ( check_item )

if check_bits_encoded != check_bits :

invalid_bits = []

for check_bit_encoded , value in check_bits_encoded . items ():

if check_bits [ check_bit_encoded ] != value :

invalid_bits . append ( check_bit_encoded )

num_bit = sum ( invalid_bits )

encoded_chunk = » . format (

encoded_chunk [: num_bit — 1 ],

int ( encoded_chunk [ num_bit — 1 ]) ^ 1 ,

encoded_chunk [ num_bit :])

return encoded_chunk

def get_diff_index_list ( value_bin1 , value_bin2 ):

«»»

Получить список индексов различающихся битов

«»»

diff_index_list = []

for index , char_bin_items in enumerate ( zip ( list ( value_bin1 ), list ( value_bin2 )), 1 ):

if char_bin_items [ 0 ] != char_bin_items [ 1 ]:

diff_index_list . append ( index )

return diff_index_list

def encode ( source ):

«»»

Кодирование данных

«»»

text_bin = chars_to_bin ( source )

result = »

for chunk_bin in chunk_iterator ( text_bin ):

chunk_bin = set_check_bits ( chunk_bin )

result += chunk_bin

return result

def decode ( encoded , fix_errors = True ):

«»»

Декодирование данных

«»»

decoded_value = »

fixed_encoded_list = []

for encoded_chunk in chunk_iterator ( encoded , CHUNK_LENGTH + len ( CHECK_BITS )):

if fix_errors :

encoded_chunk = check_and_fix_error ( encoded_chunk )

fixed_encoded_list . append ( encoded_chunk )

clean_chunk_list = []

for encoded_chunk in fixed_encoded_list :

encoded_chunk = exclude_check_bits ( encoded_chunk )

clean_chunk_list . append ( encoded_chunk )

for clean_chunk in clean_chunk_list :

for clean_char in [ clean_chunk [ i : i + 8 ] for i in range ( len ( clean_chunk )) if not i % 8 ]:

decoded_value += chr ( int ( clean_char , 2 ))

return decoded_value

if __name__ == ‘__main__’ :

source = input ( ‘Укажите текст для кодирования/декодирования:’ )

print ( ‘Длина блока кодирования: ‘ . format ( CHUNK_LENGTH ))

print ( ‘Контрольные биты: ‘ . format ( CHECK_BITS ))

encoded = encode ( source )

print ( ‘Закодированные данные: ‘ . format ( encoded ))

decoded = decode ( encoded )

print ( ‘Результат декодирования: ‘ . format ( decoded ))

encoded_with_error = set_errors ( encoded )

print ( ‘Допускаем ошибки в закодированных данных: ‘ . format ( encoded_with_error ))

diff_index_list = get_diff_index_list ( encoded , encoded_with_error )

print ( ‘Допущены ошибки в битах: ‘ . format ( diff_index_list ))

decoded = decode ( encoded_with_error , fix_errors = False )

print ( ‘Результат декодирования ошибочных данных без исправления ошибок: ‘ . format ( decoded ))

decoded = decode ( encoded_with_error )

print ( ‘Результат декодирования ошибочных данных с исправлением ошибок: ‘ . format ( decoded ))

Источник

shivamb45 / hamming-code-74-encode.py

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

# Hamming (7,4) Coding

#

# Reads binary stream from standard input and outputs Hamming (7,4) encoded

# version to standard output.

#

# USAGE: python hamming-code-74-encode.py

#

# EXAMPLE:

# $ python hamming-code-74-encode.py

# Enter Input String of bits —

# 0001

# Output — 1101001

# AUTHOR: Shivam Bharadwaj

# FORK-DATE: 2017-04-19

#

#

# ORIGINAL AUTHOR: Mark Reid

# ORGINAL CREATION DATE: 2013-10-21

K = 4

#works only for 7,4

def encode ( s ):

# Read in K=4 bits at a time and write out those plus parity bits

while len ( s ) >= K :

nibble = s [ 0 : K ]

input ( hamming ( nibble ))

s = s [ K :]

def hamming ( bits ):

# Return given 4 bits plus parity bits for bits (1,2,3), (2,3,4) and (1,3,4)

t1 = parity ( bits , [ 0 , 1 , 3 ])

t2 = parity ( bits , [ 0 , 2 , 3 ])

t3 = parity ( bits , [ 1 , 2 , 3 ])

return t1 + t2 + bits [ 0 ] + t3 + bits [ 1 :] #again saying, works only for 7,4

def parity ( s , indicies ):

# Compute the parity bit for the given string s and indicies

sub = «»

for i in indicies :

sub += s [ i ]

return str ( str . count ( sub , «1» ) % 2 )

if __name__ == «__main__» :

print ( «Enter Input String of bits — » ) #just for testing

input_string = input (). strip ()

print ( » Output — » , end = ‘ ‘ ) #just for testing

encode ( input_string )

Источник