task2.py - master - ku11ch/Lab_2

task2.py
139 строк5 KB
ku11ch
upload files
14 окт 2025, 10:46
14 окт 2025, 10:468a1e0cb
# rs_encoding.py
# Реализация кодирования RS(7,3) двумя способами

from gf8_library import GF8


def rs_encode_evaluation(message, gf):
    """
    Кодирование RS(7,3) в оценочной форме
    message = [c0, c1, c2] соответствует многочлену c0 + c1*x + c2*x²
    """
    if len(message) != 3:
        raise ValueError("Сообщение должно быть длины 3")

    codeword = []

    # Вычисляем значения в точках α⁰, α¹, α², α³, α⁴, α⁵, α⁶
    for i in range(7):
        point = gf.pow(gf.alpha, i)  # αⁱ
        value = 0
        power = 1

        # Вычисляем m(point) = c0 + c1*point + c2*point²
        for coeff in message:
            term = gf.mul(coeff, power)
            value = gf.add(value, term)
            power = gf.mul(power, point)

        codeword.append(value)

    return codeword


def rs_encode_generator(message, gf):
    """
    Кодирование RS(7,3) через генераторный многочлен
    message = [c0, c1, c2] - информационные символы
    """
    if len(message) != 3:
        raise ValueError("Сообщение должно быть длины 3")

    # Генераторный многочлен для RS(7,3): g(x) = (x-α)(x-α²)(x-α³)(x-α⁴)
    # Вычисляем коэффициенты g(x)

    # Начинаем с g(x) = 1
    g_poly = [1]

    # Умножаем на (x + α^i) для i=1,2,3,4
    for i in range(1, 5):
        root = gf.pow(gf.alpha, i)
        # Новый полином: g_poly * (x + root)
        new_poly = [0] * (len(g_poly) + 1)

        for j, coeff in enumerate(g_poly):
            # coeff * x
            new_poly[j + 1] = gf.add(new_poly[j + 1], coeff)
            # coeff * root
            new_poly[j] = gf.add(new_poly[j], gf.mul(coeff, root))

        g_poly = new_poly

    print(f"Генераторный многочлен g(x): {[gf.to_poly_str(c) for c in g_poly]}")

    # Многочлен сообщения: m(x) = c0 + c1*x + c2*x²
    # Умножаем на x⁴: x⁴ * m(x) = c0*x⁴ + c1*x⁵ + c2*x⁶
    message_poly = message + [0, 0, 0, 0]

    # Деление полиномов (простая реализация)
    remainder = message_poly.copy()

    # Выполняем деление
    for i in range(3):  # для 3 информационных символов
        if remainder[i] != 0:
            factor = remainder[i]
            for j in range(len(g_poly)):
                if g_poly[j] != 0:
                    remainder[i + j] = gf.add(remainder[i + j], gf.mul(factor, g_poly[j]))

    # Кодовое слово = сообщение + контрольные символы (остаток)
    codeword = message + remainder[3:7]

    return codeword


def compare_encoding_methods(gf):
    """Сравнение двух методов кодирования"""
    print("=== Сравнение методов кодирования RS(7,3) ===")

    # Тестовое сообщение: 1 + x (коэффициенты [1, 1, 0])
    message = [0b001, 0b001, 0b000]
    print(f"Исходное сообщение: {[gf.to_poly_str(m) for m in message]}")
    print(f"Соответствует многочлену: {gf.to_poly_str(message[0])} + {gf.to_poly_str(message[1])}*x")

    # Кодирование оценочной формой
    codeword_eval = rs_encode_evaluation(message, gf)
    print(f"\n1. Оценочная форма:")
    print(f"   Кодовое слово: {[format(c, '03b') for c in codeword_eval]}")
    print(f"   Полиномы: {[gf.to_poly_str(c) for c in codeword_eval]}")

    # Кодирование генераторным многочленом
    codeword_gen = rs_encode_generator(message, gf)
    print(f"\n2. Генераторный метод:")
    print(f"   Кодовое слово: {[format(c, '03b') for c in codeword_gen]}")
    print(f"   Полиномы: {[gf.to_poly_str(c) for c in codeword_gen]}")

    # Проверка совпадения
    if codeword_eval == codeword_gen:
        print(f"\n✓ Методы дают одинаковый результат!")
    else:
        print(f"\n✗ Методы дают разный результат!")

    return codeword_eval, codeword_gen


def test_different_messages(gf):
    """Тестирование на разных сообщениях"""
    print("\n=== Тестирование на разных сообщениях ===")

    test_messages = [
        [0b001, 0b001, 0b000],  # 1 + x
        [0b010, 0b000, 0b000],  # x
        [0b001, 0b000, 0b100],  # 1 + x²
        [0b011, 0b101, 0b110],  # x+1 + (x²+1)x + (x²+x)x²
    ]

    for i, message in enumerate(test_messages):
        print(f"\nСообщение {i + 1}: {[gf.to_poly_str(m) for m in message]}")
        codeword_eval = rs_encode_evaluation(message, gf)
        codeword_gen = rs_encode_generator(message, gf)

        print(f"  Оценочная:  {[format(c, '03b') for c in codeword_eval]}")
        print(f"  Генераторная: {[format(c, '03b') for c in codeword_gen]}")
        print(f"  Совпадают: {codeword_eval == codeword_gen}")


if __name__ == "__main__":
    gf = GF8()
    compare_encoding_methods(gf)
    test_different_messages(gf)