-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathgalois_field.py
115 lines (99 loc) · 5.17 KB
/
galois_field.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
# galois_field.py
#
# Copyright (c) 2005--2015 by Sidney Cadot <sidney@jigsaw.nl>
# This software is licensed under the GNU General Public License (GPL).
#
# This file is part of laser2wav, a software-only implementation of
# an audio CD decoder.
# Elements of GF(256) are represented as 8-bit unsigned integers, with
# the LSB representing 'x^0', and the MSB representing 'x^7'.
#
# The field is generated by the polynomial
#
# g(x) = x^8 + x^4 + x^3 + x^2 + 1
#
# The primitive element alpha corresponds to the polynomial "x" here;
# which means that alpha is represented as 00000010 (bin) = 2 (dec).
# the generator polynomial
generator = (1<<8) + (1<<4) + (1<<3) + (1<<2) + (1<<0)
# the zero element
zero = 0
# the primitive element alpha
alpha = (1<<1)
# Below are Power, Logarithm, Multiplication, and Addition functions for
# GF(2^8) as used in Compact Discs for Reed-Solomon encoding/decoding.
# For all integers i, gf_alpha_power_table[i%255] == (alpha) ** i,
# where alpha is the primitive element represented by the byte '2'.
# Note that the zero element (represented by the byte '0') cannot be
# represented as a power of alpha.
# This table can easily be generated as follows:
#
# poly = 1
# alpha_power_table = []
# for i in range(255):
# alpha_power_table.append(poly)
# poly = poly << 1
# if poly >= (1<<8):
# poly = add(poly, generator) # reduce modulo (generator)
alpha_power_table = [
1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38,
76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192,
157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35,
70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161,
95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240,
253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226,
217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52, 104, 208, 189, 103, 206,
129, 31, 62, 124, 248, 237, 199, 147, 59, 118, 236, 197, 151, 51, 102, 204,
133, 23, 46, 92, 184, 109, 218, 169, 79, 158, 33, 66, 132, 21, 42, 84,
168, 77, 154, 41, 82, 164, 85, 170, 73, 146, 57, 114, 228, 213, 183, 115,
230, 209, 191, 99, 198, 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255,
227, 219, 171, 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65,
130, 25, 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166,
81, 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9,
18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 22,
44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 142 ]
# For all elements 'e' except the zero element, alpha ^ gf_alpha_logarithm_table[e-1] == e,
# where alpha is the primitive element represented by the byte '2'.
# Note that the zero element (represented by the byte '0') cannot be
# represented as a power of alpha, i.e. its logarithm does not exist.
#
# This table can be derived from the alpha_power_table as follows:
#
# alpha_logarithm_table = []
# for e in range(1, 256):
# alpha_logarithm_table.append(alpha_power_table.index(e))
alpha_logarithm_table = [
0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4,
100, 224, 14, 52, 141, 239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 5,
138, 101, 47, 225, 36, 15, 33, 53, 147, 142, 218, 240, 18, 130, 69, 29,
181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 114, 166, 6,
191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 145, 34, 136, 54,
208, 148, 206, 143, 150, 219, 189, 241, 210, 19, 92, 131, 56, 70, 64, 30,
66, 182, 163, 195, 72, 126, 110, 107, 58, 40, 84, 250, 133, 186, 61, 202,
94, 155, 159, 10, 21, 121, 43, 78, 212, 229, 172, 115, 243, 167, 87, 7,
112, 192, 247, 140, 128, 99, 13, 103, 74, 222, 237, 49, 197, 254, 24, 227,
165, 153, 119, 38, 184, 180, 124, 17, 68, 146, 217, 35, 32, 137, 46, 55,
63, 209, 91, 149, 188, 207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242,
86, 211, 171, 20, 42, 93, 158, 132, 60, 57, 83, 71, 109, 65, 162, 31,
45, 67, 216, 183, 123, 164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108,
161, 59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203,
89, 95, 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215, 79,
174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168, 80, 88, 175 ]
def alpha_power(i):
# note that in Python, (negative_int % positive_int) is (sensibly!)
# defined to yield a nonnegative integer, so this function also works
# for negative arguments.
return alpha_power_table[i % 255]
def alpha_logarithm(e):
assert e != zero # we cannot take the logarithm of the zero element.
return alpha_logarithm_table[e - 1]
def add(a, b):
return (a ^ b) # xor operator
def multiply(a, b):
if (a == 0) or (b == 0):
return 0
else:
return alpha_power(alpha_logarithm(a) + alpha_logarithm(b))
def power(e, i):
assert e != zero # leave undefined, even though we could define it.
return alpha_power(alpha_logarithm(e) * i)