Trofimov Solver

trofimov_solver.py

import galois
import io


class StringIOWithEnd(io.StringIO):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.end = "\n"

    def write(self, s="", end="\n"):
        super().write(s + end)


# Определяем поле Галуа GF(2^4)
GF = galois.GF(2**4, repr="power")

# Примитивный элемент α
alpha = GF.primitive_element

# Максимум исправляемых ошибок
t = 3

# Принятый вектор v
v = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1]
# v = [1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0]
# v = [1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]


def get_solution(v):
    steps = [StringIOWithEnd()]

    # Построение многочлена v(x)
    v_poly = galois.Poly(
        v[::-1], field=GF
    )  # Инвертируем порядок, так как младший коэффициент идет первым

    steps[-1].write(f"Принятый вектор v(x) = {v_poly}")

    steps.append(StringIOWithEnd())

    # --- part 1 ---

    # Вычисление синдромов S1, S3, S5
    steps[-1].write(
        "Пошаговые вычисления синдромов (cначала подставляем, потом сокращаем):\n"
    )

    syndromes = {}

    for j in range(1, 2 * t, 2):  # Нечетные индексы: 1, 3, 5
        # Вычисление S_j
        steps[-1].write(f"S{j} = v(α^{j}) = ")
        components_orig, components = [], []
        for power, coeff in enumerate(v[::1]):  # Прямой порядок для многочлена
            if coeff == 1:
                term = alpha ** (power * j % 15)  # Умножение степени в поле GF(2^4)
                components_orig.append(f"α^{power * j}")
                components.append(f"α^{power * j % 15}")

        steps[-1].write(f"= {' + '.join(components_orig)} =")
        steps[-1].write(f"= {' + '.join(components)} =")

        S_j = v_poly(alpha**j)
        syndromes[j] = S_j
        steps[-1].write(f"= {bin(int(S_j))[2:].zfill(4)} = {str(S_j)}\n")

    steps.append(StringIOWithEnd())

    # Итоговые синдромы
    steps[-1].write("Итоговые синдромы:\n")
    for j, S_j in syndromes.items():
        steps[-1].write(f"S{j} = {str(S_j)}")

    steps.append(StringIOWithEnd())

    # --- part 2 ---

    steps[-1].write("Пошаговые вычисления коэффициентов многочлена локаторов ошибок:\n")

    # Calculate error locator polynomial coefficients (assuming 3 errors)
    Lambda1 = syndromes[1]
    Lambda2 = None
    Lambda3 = None

    steps[-1].write(f"λ1 = S1 = {str(syndromes[1])}\n")

    # Check case "в"
    try:
        Lambda2 = (syndromes[1] ** 2 * syndromes[3] + syndromes[5]) * (
            syndromes[1] ** 3 + syndromes[3]
        ) ** (-1)
        Lambda3 = syndromes[1] ** 3 + syndromes[3] + syndromes[1] * Lambda2

        steps[-1].write(f"λ2 = (S1^2 * S3 + S5) * (S1^3 + S3)^-1 = ", end="")
        steps[-1].write(
            f"(({str(syndromes[1])})^2 * {str(syndromes[3])} + {str(syndromes[5])})) * ",
            end="",
        )
        steps[-1].write(
            f"(({str(syndromes[1])})^3 + {str(syndromes[3])})^-1 = {str(Lambda2)}\n"
        )
        steps[-1].write(f"λ3 = (S1^3 + S3) + S1 * λ2 = ", end="")
        steps[-1].write(
            f"(({str(syndromes[1])})^3 + {str(syndromes[3])}) + {str(syndromes[1])} * {str(Lambda2)} = {str(Lambda3)}"
        )

    except ZeroDivisionError:
        # Handle the case when (syndromes[1]**3 + syndromes[3]) is zero (reduce as sumed error count)

        steps[-1].write(
            f"Внимание: Требуется найти обратное значение к нулевому элементу поля:\n"
        )
        steps[-1].write(f"λ2 = (S1^2 * S3 + S5) * (S1^3 + S3)^-1 = ", end="")
        steps[-1].write(
            f"(({str(syndromes[1])})^2 * {str(syndromes[3])} + {str(syndromes[5])})) * ",
            end="",
        )
        steps[-1].write(f"(({str(syndromes[1])})^3 + {str(syndromes[3])})^-1")
        steps[-1].write(
            f" -> (({str(syndromes[1])})^3 + {str(syndromes[3])})^-1 = 0^-1 = невозможно\n"
        )
        steps[-1].write(
            f"Соттветственно код не может найти три ошибки. Попробуем найти две ошибки."
        )
        steps[-1].write(f"\nВычисляем λ2 по другой формуле:")

        Lambda2 = (syndromes[3] + syndromes[1] ** 3) * syndromes[1] ** (-1)
        steps[-1].write(f"λ2 = (S3 + S1^3) * S1^-1 = ", end="")
        steps[-1].write(
            f"({str(syndromes[3])} + ({str(syndromes[1])})^3) * ({str(syndromes[1])})^-1 = {str(Lambda2)}"
        )

    steps.append(StringIOWithEnd())

    steps[-1].write("Значения коэффициентов многочлена локаторов ошибок:\n")

    steps[-1].write(f"λ1 = {str(Lambda1)}")
    if Lambda2 is not None:
        steps[-1].write(f"λ2 = {str(Lambda2)}")
    if Lambda3 is not None:
        steps[-1].write(f"λ3 = {str(Lambda3)}")

    steps.append(StringIOWithEnd())

    num_errors = 3 if Lambda3 else 2 if Lambda2 else 1

    steps[-1].write(
        f"Количество ошибок которые предстоит найти (оно же число корней многочлена): {num_errors}"
    )

    steps.append(StringIOWithEnd())

    # --- part 3 ---

    # Создаем многочлен локаторов ошибок Λ(x)
    lambda_coeffs = [1]  # Свободный член всегда 1

    if Lambda1 is not None:
        lambda_coeffs.append(Lambda1)
    if Lambda2 is not None:
        lambda_coeffs.append(Lambda2)
    if Lambda3 is not None:
        lambda_coeffs.append(Lambda3)

    lambda_poly = galois.Poly(lambda_coeffs[::-1], field=GF)

    steps[-1].write("Многочлен локаторов ошибок:\n")
    steps[-1].write(f"λ(x) = {str(lambda_poly)}")

    steps.append(StringIOWithEnd())

    steps[-1].write("Поиск корней многочлена локаторов ошибок:\n")

    roots = []
    for j in range(0, 15):
        components_orig, components = ["1"], ["1"]
        for i, c in enumerate(lambda_coeffs[1:]):
            if c != 0:
                component = f"α^{j * (i + 1)}"
                if c != 1:
                    component = f"{str(c)} * {component}"
                components_orig.append(component)

        result = lambda_poly(alpha**j)
        steps[-1].write(f"λ(α^{j}) = {' + '.join(components_orig)} = {str(result)}")
        if result == 0:
            roots.append(GF(alpha**j))
            steps[-1].write(f"\nНайден корень: α^{str(j)}\n")

            if len(roots) == num_errors:
                steps[-1].write(
                    f"Найдено достаточное количество корней для исправления ошибок: {num_errors}"
                )
                if j != 14:
                    steps.append(StringIOWithEnd())
                    steps[-1].write(
                        "Однако выводим все остальные рассчеты для проверки (это можно не писать):\n"
                    )

    assert sorted(roots) == sorted(
        lambda_poly.roots()
    )  # Проверка корректности вычисления корней

    steps.append(StringIOWithEnd())

    steps[-1].write(
        f"Найденные корни многочлена локаторов ошибок: {', '.join([str(root) for root in roots])}"
    )

    steps.append(StringIOWithEnd())

    steps[-1].write("Вычисляем позиции ошибок:\n")

    err_positions = []
    for root in roots:
        steps[-1].write(f"{str(root)} -> ({str(root)})^-1 = {str(root**-1)}")
        err_positions.append((root**-1).log())

    steps[-1].write(f"\nПозиции ошибок: {sorted(err_positions)}")

    return [step.getvalue().rstrip() for step in steps]


for i in get_solution(v):
    print(f"{i}\n")

trofimov_solver_example_output.txt

Вектор v: [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1]

Принятый вектор v(x) = x^14 + x^12 + x^10 + x^9 + x^8 + x^7 + x^6 + x^2 + x + 1

Пошаговые вычисления синдромов (cначала подставляем, потом сокращаем):

S1 = v(α^1) = 
= α^0 + α^2 + α^4 + α^5 + α^6 + α^7 + α^8 + α^12 + α^13 + α^14 =
= α^0 + α^2 + α^4 + α^5 + α^6 + α^7 + α^8 + α^12 + α^13 + α^14 =
= 1110 = α^11

S3 = v(α^3) = 
= α^0 + α^6 + α^12 + α^15 + α^18 + α^21 + α^24 + α^36 + α^39 + α^42 =
= α^0 + α^6 + α^12 + α^0 + α^3 + α^6 + α^9 + α^6 + α^9 + α^12 =
= 0110 = α^5

S5 = v(α^5) = 
= α^0 + α^10 + α^20 + α^25 + α^30 + α^35 + α^40 + α^60 + α^65 + α^70 =
= α^0 + α^10 + α^5 + α^10 + α^0 + α^5 + α^10 + α^0 + α^5 + α^10 =
= 0001 = 1

Итоговые синдромы:

S1 = α^11
S3 = α^5
S5 = 1

Пошаговые вычисления коэффициентов многочлена локаторов ошибок:

λ1 = S1 = α^11

λ2 = (S1^2 * S3 + S5) * (S1^3 + S3)^-1 = ((α^11)^2 * α^5 + 1)) * ((α^11)^3 + α^5)^-1 = 1

λ3 = (S1^3 + S3) + S1 * λ2 = ((α^11)^3 + α^5) + α^11 * 1 = 0

Значения коэффициентов многочлена локаторов ошибок:

λ1 = α^11
λ2 = 1
λ3 = 0

Количество ошибок которые предстоит найти (оно же число корней многочлена): 2

Многочлен локаторов ошибок:

λ(x) = x^2 + (α^11)x + 1

Поиск корней многочлена локаторов ошибок:

λ(α^0) = 1 + α^11 * α^0 + α^0 = α^11
λ(α^1) = 1 + α^11 * α^1 + α^2 = α^9
λ(α^2) = 1 + α^11 * α^2 + α^4 = α^12
λ(α^3) = 1 + α^11 * α^3 + α^6 = α^2
λ(α^4) = 1 + α^11 * α^4 + α^8 = α^8
λ(α^5) = 1 + α^11 * α^5 + α^10 = α^2
λ(α^6) = 1 + α^11 * α^6 + α^12 = α^9
λ(α^7) = 1 + α^11 * α^7 + α^14 = 0

Найден корень: α^7

λ(α^8) = 1 + α^11 * α^8 + α^16 = 0

Найден корень: α^8

Найдено достаточное количество корней для исправления ошибок: 2

Однако выводим все остальные рассчеты для проверки (это можно не писать):

λ(α^9) = 1 + α^11 * α^9 + α^18 = α^12
λ(α^10) = 1 + α^11 * α^10 + α^20 = α^7
λ(α^11) = 1 + α^11 * α^11 + α^22 = 1
λ(α^12) = 1 + α^11 * α^12 + α^24 = α^11
λ(α^13) = 1 + α^11 * α^13 + α^26 = α^8
λ(α^14) = 1 + α^11 * α^14 + α^28 = α^7

Найденные корни многочлена локаторов ошибок: α^7, α^8

Вычисляем позиции ошибок:

α^7 -> (α^7)^-1 = α^8
α^8 -> (α^8)^-1 = α^7

Позиции ошибок: [7, 8]