TheAlgorithms-Python

1
# Author: João Gustavo A. Amorim & Gabriel Kunz
2
# Author email: joaogustavoamorim@gmail.com and gabriel-kunz@uergs.edu.br
3
# Coding date:  apr 2019
4
# Black: True
5

6
"""
7
* This code implement the Hamming code:
8
    https://en.wikipedia.org/wiki/Hamming_code - In telecommunication,
9
Hamming codes are a family of linear error-correcting codes. Hamming
10
codes can detect up to two-bit errors or correct one-bit errors
11
without detection of uncorrected errors. By contrast, the simple
12
parity code cannot correct errors, and can detect only an odd number
13
of bits in error. Hamming codes are perfect codes, that is, they
14
achieve the highest possible rate for codes with their block length
15
and minimum distance of three.
16

17
* the implemented code consists of:
18
    * a function responsible for encoding the message (emitterConverter)
19
        * return the encoded message
20
    * a function responsible for decoding the message (receptorConverter)
21
        * return the decoded message and a ack of data integrity
22

23
* how to use:
24
        to be used you must declare how many parity bits (sizePari)
25
    you want to include in the message.
26
        it is desired (for test purposes) to select a bit to be set
27
    as an error. This serves to check whether the code is working correctly.
28
        Lastly, the variable of the message/word that must be desired to be
29
    encoded (text).
30

31
* how this work:
32
        declaration of variables (sizePari, be, text)
33

34
        converts the message/word (text) to binary using the
35
    text_to_bits function
36
        encodes the message using the rules of hamming encoding
37
        decodes the message using the rules of hamming encoding
38
        print the original message, the encoded message and the
39
    decoded message
40

41
        forces an error in the coded text variable
42
        decodes the message that was forced the error
43
        print the original message, the encoded message, the bit changed
44
    message and the decoded message
45
"""
46

47
# Imports
48
import numpy as np
49

50

51
# Functions of binary conversion--------------------------------------
52
def text_to_bits(text, encoding="utf-8", errors="surrogatepass"):
53
    """
54
    >>> text_to_bits("msg")
55
    '011011010111001101100111'
56
    """
57
    bits = bin(int.from_bytes(text.encode(encoding, errors), "big"))[2:]
58
    return bits.zfill(8 * ((len(bits) + 7) // 8))
59

60

61
def text_from_bits(bits, encoding="utf-8", errors="surrogatepass"):
62
    """
63
    >>> text_from_bits('011011010111001101100111')
64
    'msg'
65
    """
66
    n = int(bits, 2)
67
    return n.to_bytes((n.bit_length() + 7) // 8, "big").decode(encoding, errors) or "\0"
68

69

70
# Functions of hamming code-------------------------------------------
71
def emitter_converter(size_par, data):
72
    """
73
    :param size_par: how many parity bits the message must have
74
    :param data:  information bits
75
    :return: message to be transmitted by unreliable medium
76
            - bits of information merged with parity bits
77

78
    >>> emitter_converter(4, "101010111111")
79
    ['1', '1', '1', '1', '0', '1', '0', '0', '1', '0', '1', '1', '1', '1', '1', '1']
80
    >>> emitter_converter(5, "101010111111")
81
    Traceback (most recent call last):
82
        ...
83
    ValueError: size of parity don't match with size of data
84
    """
85
    if size_par + len(data) <= 2**size_par - (len(data) - 1):
86
        raise ValueError("size of parity don't match with size of data")
87

88
    data_out = []
89
    parity = []
90
    bin_pos = [bin(x)[2:] for x in range(1, size_par + len(data) + 1)]
91

92
    # sorted information data for the size of the output data
93
    data_ord = []
94
    # data position template + parity
95
    data_out_gab = []
96
    # parity bit counter
97
    qtd_bp = 0
98
    # counter position of data bits
99
    cont_data = 0
100

101
    for x in range(1, size_par + len(data) + 1):
102
        # Performs a template of bit positions - who should be given,
103
        # and who should be parity
104
        if qtd_bp < size_par:
105
            if (np.log(x) / np.log(2)).is_integer():
106
                data_out_gab.append("P")
107
                qtd_bp = qtd_bp + 1
108
            else:
109
                data_out_gab.append("D")
110
        else:
111
            data_out_gab.append("D")
112

113
        # Sorts the data to the new output size
114
        if data_out_gab[-1] == "D":
115
            data_ord.append(data[cont_data])
116
            cont_data += 1
117
        else:
118
            data_ord.append(None)
119

120
    # Calculates parity
121
    qtd_bp = 0  # parity bit counter
122
    for bp in range(1, size_par + 1):
123
        # Bit counter one for a given parity
124
        cont_bo = 0
125
        # counter to control the loop reading
126
        for cont_loop, x in enumerate(data_ord):
127
            if x is not None:
128
                try:
129
                    aux = (bin_pos[cont_loop])[-1 * (bp)]
130
                except IndexError:
131
                    aux = "0"
132
                if aux == "1" and x == "1":
133
                    cont_bo += 1
134
        parity.append(cont_bo % 2)
135

136
        qtd_bp += 1
137

138
    # Mount the message
139
    cont_bp = 0  # parity bit counter
140
    for x in range(size_par + len(data)):
141
        if data_ord[x] is None:
142
            data_out.append(str(parity[cont_bp]))
143
            cont_bp += 1
144
        else:
145
            data_out.append(data_ord[x])
146

147
    return data_out
148

149

150
def receptor_converter(size_par, data):
151
    """
152
    >>> receptor_converter(4, "1111010010111111")
153
    (['1', '0', '1', '0', '1', '0', '1', '1', '1', '1', '1', '1'], True)
154
    """
155
    # data position template + parity
156
    data_out_gab = []
157
    # Parity bit counter
158
    qtd_bp = 0
159
    # Counter p data bit reading
160
    cont_data = 0
161
    # list of parity received
162
    parity_received = []
163
    data_output = []
164

165
    for i, item in enumerate(data, 1):
166
        # Performs a template of bit positions - who should be given,
167
        #  and who should be parity
168
        if qtd_bp < size_par and (np.log(i) / np.log(2)).is_integer():
169
            data_out_gab.append("P")
170
            qtd_bp = qtd_bp + 1
171
        else:
172
            data_out_gab.append("D")
173

174
        # Sorts the data to the new output size
175
        if data_out_gab[-1] == "D":
176
            data_output.append(item)
177
        else:
178
            parity_received.append(item)
179

180
    # -----------calculates the parity with the data
181
    data_out = []
182
    parity = []
183
    bin_pos = [bin(x)[2:] for x in range(1, size_par + len(data_output) + 1)]
184

185
    #  sorted information data for the size of the output data
186
    data_ord = []
187
    # Data position feedback + parity
188
    data_out_gab = []
189
    # Parity bit counter
190
    qtd_bp = 0
191
    # Counter p data bit reading
192
    cont_data = 0
193

194
    for x in range(1, size_par + len(data_output) + 1):
195
        # Performs a template position of bits - who should be given,
196
        # and who should be parity
197
        if qtd_bp < size_par and (np.log(x) / np.log(2)).is_integer():
198
            data_out_gab.append("P")
199
            qtd_bp = qtd_bp + 1
200
        else:
201
            data_out_gab.append("D")
202

203
        # Sorts the data to the new output size
204
        if data_out_gab[-1] == "D":
205
            data_ord.append(data_output[cont_data])
206
            cont_data += 1
207
        else:
208
            data_ord.append(None)
209

210
    # Calculates parity
211
    qtd_bp = 0  # parity bit counter
212
    for bp in range(1, size_par + 1):
213
        # Bit counter one for a certain parity
214
        cont_bo = 0
215
        for cont_loop, x in enumerate(data_ord):
216
            if x is not None:
217
                try:
218
                    aux = (bin_pos[cont_loop])[-1 * (bp)]
219
                except IndexError:
220
                    aux = "0"
221
                if aux == "1" and x == "1":
222
                    cont_bo += 1
223
        parity.append(str(cont_bo % 2))
224

225
        qtd_bp += 1
226

227
    # Mount the message
228
    cont_bp = 0  # Parity bit counter
229
    for x in range(size_par + len(data_output)):
230
        if data_ord[x] is None:
231
            data_out.append(str(parity[cont_bp]))
232
            cont_bp += 1
233
        else:
234
            data_out.append(data_ord[x])
235

236
    ack = parity_received == parity
237
    return data_output, ack
238

239

240
# ---------------------------------------------------------------------
241
"""
242
# Example how to use
243

244
# number of parity bits
245
sizePari = 4
246

247
# location of the bit that will be forced an error
248
be = 2
249

250
# Message/word to be encoded and decoded with hamming
251
# text = input("Enter the word to be read: ")
252
text = "Message01"
253

254
# Convert the message to binary
255
binaryText = text_to_bits(text)
256

257
# Prints the binary of the string
258
print("Text input in binary is '" + binaryText + "'")
259

260
# total transmitted bits
261
totalBits = len(binaryText) + sizePari
262
print("Size of data is " + str(totalBits))
263

264
print("\n --Message exchange--")
265
print("Data to send ------------> " + binaryText)
266
dataOut = emitterConverter(sizePari, binaryText)
267
print("Data converted ----------> " + "".join(dataOut))
268
dataReceiv, ack = receptorConverter(sizePari, dataOut)
269
print(
270
    "Data receive ------------> "
271
    + "".join(dataReceiv)
272
    + "\t\t -- Data integrity: "
273
    + str(ack)
274
)
275

276

277
print("\n --Force error--")
278
print("Data to send ------------> " + binaryText)
279
dataOut = emitterConverter(sizePari, binaryText)
280
print("Data converted ----------> " + "".join(dataOut))
281

282
# forces error
283
dataOut[-be] = "1" * (dataOut[-be] == "0") + "0" * (dataOut[-be] == "1")
284
print("Data after transmission -> " + "".join(dataOut))
285
dataReceiv, ack = receptorConverter(sizePari, dataOut)
286
print(
287
    "Data receive ------------> "
288
    + "".join(dataReceiv)
289
    + "\t\t -- Data integrity: "
290
    + str(ack)
291
)
292
"""
293