直接的な復号法(2重誤りまで)のプログラム

上記noteについてプログラムを作成した。
このプログラムを用いて受信語が誤った符号語に訂正(訂正誤り)されてしまうケースを観察する。

プログラム

# coding: utf-8

table_v2e = {}
table_e2v = {}
# 多項式の次数
deg = 0
#原始元の位数
order = 0

def list2bin(l):
     out = 0
     for bit in l[::-1]:
         out = (out << 1) | (1 if bit else 0)
     return out

def Galois_sum(a, b):
    return a^b

def Galois_prod(a, b):
    if a == 0 or b == 0:
        return 0
    a_e = table_v2e[a]
    b_e = table_v2e[b]
    a_b_prod_e = (a_e + b_e) % order
    return table_e2v[a_b_prod_e]
    
def Galois_div(a, b):
    if a == 0:
        return 0
    a_e = table_v2e[a]
    b_e = table_v2e[b]
    a_b_div_e = (a_e - b_e) % order
    return table_e2v[a_b_div_e]


# a3*x^3 + a2*x^2 + a1*x + a0 -> [a0, a1, a2, a3]
def Galois(primitive_func):
    deg = len(primitive_func) - 1
    order = 2**deg - 1
    print("Primitive Function: ", end="")
    print(primitive_func)
    print("--------------")
    print("Galois Field("+str(order+1)+")")
    # ret = primitive_func[:-1].copy()
    ret = [False] * deg
    ret[0] = True
    tmp_digit = 0
    table_e2v[0] = list2bin(ret)
    table_v2e[list2bin(ret)] = 0
    print("alpha^0:", end='')
    print(ret)
    for j in range(order):
        print("alpha^"+str(j + 1)+":", end='')
        
        carry = ret[deg-1]
        for i in range(deg-1, -1, -1):
            if i == 0:
                tmp_digit = False
            else:
                tmp_digit = ret[i-1]
            if carry:
                tmp_digit = tmp_digit ^ primitive_func[i]
            ret[i] = tmp_digit
        if j+1 < order:
            table_e2v[j+1] = list2bin(ret)
            table_v2e[list2bin(ret)] = j+1
        print(ret)
        
    return order
    
def syndrome1(v):
    ret = 0
    i = 0

    for v_i in v:
        if v_i:
            ret = Galois_sum(ret, table_e2v[i])
        i = (i + 1) % order
        
    return ret

def syndrome3(v):
    ret = 0
    i = 0
    for v_i in v:
        if v_i:
            ret = Galois_sum(ret, table_e2v[i])
        i = (i + 3) % order
        
    return ret

# solve error location polynomial
def solve_error_location_polynomial(coefficient1, coefficient2):
    locators = []
    for i in table_v2e.keys():
        i_pow2 = Galois_prod(i, i)
        t1 = 1
        t2 = Galois_prod(coefficient1, i)
        t3 = Galois_prod(coefficient2, i_pow2)
        tmp = Galois_sum(t1, t2)
        tmp = Galois_sum(tmp, t3)
        if tmp == 0:
            locator = Galois_div(1, i)
            locators.append(locator)
    return locators

def correct(v):
    print("v:" + str(v))
    s1 = syndrome1(v)
    print("s1:" + bin(s1))
    s3 = syndrome3(v)
    print("s3:" + bin(s3))
    
    if s1 == 0:
        print("No Error!")
        return v

    s1_pow2 = Galois_prod(s1, s1)
    
    s3_by_s1 = Galois_div(s3, s1)
    coefficient2 = Galois_sum(s1_pow2, s3_by_s1)
    print("s1**2:" + bin(s1_pow2))
    print("coefficient2:"+ bin(coefficient2))
    locators = solve_error_location_polynomial(s1, coefficient2)
    if len(locators) == 0:
        print("Correct Error!")
        return 
    
    for l in locators:
        l_e = table_v2e[l]
        print("error locator:"+ bin(l) + ", alpha^" + str(l_e))
        v[l_e] = v[l_e] ^ True
    print("corrected v:" + str(v))  
    
    
order = Galois([True,True,False, False, True])
print("--------------")
#correct([True, True, False, False])
correct([True, True, False, True, False, False, True, False, True, True, False, True, True, True, False])

最後の関数correct()への引数が訂正対象の受信語となっており、上記noteの受信語を使っている。
結果は以下

Primitive Function: [True, True, False, False, True]
--------------
Galois Field(16)
alpha^0:[True, False, False, False]
alpha^1:[False, True, False, False]
alpha^2:[False, False, True, False]
alpha^3:[False, False, False, True]
alpha^4:[True, True, False, False]
alpha^5:[False, True, True, False]
alpha^6:[False, False, True, True]
alpha^7:[True, True, False, True]
alpha^8:[True, False, True, False]
alpha^9:[False, True, False, True]
alpha^10:[True, True, True, False]
alpha^11:[False, True, True, True]
alpha^12:[True, True, True, True]
alpha^13:[True, False, True, True]
alpha^14:[True, False, False, True]
alpha^15:[True, False, False, False]
--------------
v:[True, True, False, True, False, False, True, False, True, True, False, True, True, True, False]
s1:0b100
s3:0b0
s1**2:0b11
coefficient2:0b11
error locator:0b1111, alpha^12
error locator:0b1011, alpha^7
corrected v:[True, True, False, True, False, False, True, True, True, True, False, True, False, True, False]

誤りロケータ(error locator)が$${\alpha^{12}, \alpha^7}$$と得られており、問題なく動作していることが分かる。

別入力でも試してみる。

上記note(直接的な復号法の動作例2)で示した、送信語"110100111101010"、誤り位置が次数0, 7, 12にあるとしたケースでは、

Primitive Function: [True, True, False, False, True]
--------------
Galois Field(16)
alpha^0:[True, False, False, False]
alpha^1:[False, True, False, False]
alpha^2:[False, False, True, False]
alpha^3:[False, False, False, True]
alpha^4:[True, True, False, False]
alpha^5:[False, True, True, False]
alpha^6:[False, False, True, True]
alpha^7:[True, True, False, True]
alpha^8:[True, False, True, False]
alpha^9:[False, True, False, True]
alpha^10:[True, True, True, False]
alpha^11:[False, True, True, True]
alpha^12:[True, True, True, True]
alpha^13:[True, False, True, True]
alpha^14:[True, False, False, True]
alpha^15:[True, False, False, False]
--------------
v:[False, True, False, True, False, False, True, False, True, True, False, True, True, True, False]
s1:0b101
s3:0b1
s1**2:0b10
coefficient2:0b1001
Correct Error!

誤り位置多項式に根がないので訂正不能である。

さて、ここから新しい入力を試してみる。同じ送信語に対して、誤り位置が次数2, 7, 12にあるとしたケースを見てみよう。