task3.py - master - ku11ch/Lab_2

task3.py
204 строки8 KB
ku11ch
upload files
14 окт 2025, 10:46
14 окт 2025, 10:468a1e0cb
# error_correction.py
# Моделирование ошибок и реализация декодера

from gf8_library import GF8


def simulate_errors(codeword, error_positions, error_values, gf):
    """
    Моделирование ошибок в канале связи
    error_positions: список позиций ошибок
    error_values: значения ошибок
    """
    corrupted = codeword.copy()

    for pos, err_val in zip(error_positions, error_values):
        if 0 <= pos < len(codeword):
            corrupted[pos] = gf.add(corrupted[pos], err_val)

    return corrupted


def compute_syndromes(received, gf, t=2):
    """
    Вычисление синдромов s₁, s₂, s₃, s₄
    t - корректирующая способность (2 для RS(7,3))
    """
    syndromes = []

    for j in range(1, 2 * t + 1):  # s₁, s₂, s₃, s₄
        s = 0
        for i, symbol in enumerate(received):
            # s_j = Σ r_i * α^(i*j)
            exponent = (i * j) % 7
            alpha_power = gf.pow(gf.alpha, exponent)
            s = gf.add(s, gf.mul(symbol, alpha_power))
        syndromes.append(s)

    return syndromes


def berlekamp_massey(syndromes, gf):
    """
    Упрощенный алгоритм Берлекэмпа-Мэсси для нахождения локатора ошибок
    """
    # Для одиночных и двойных ошибок используем упрощенный подход
    s1, s2, s3, s4 = syndromes

    if s1 == 0 and s2 == 0 and s3 == 0 and s4 == 0:
        return []  # ошибок нет

    # Пробуем найти одну ошибку
    if s1 != 0 and s2 != 0:
        error_locator = gf.mul(s2, gf.inv(s1))
        # Ищем позицию l такую, что α^l = error_locator
        for l in range(7):
            if gf.pow(gf.alpha, l) == error_locator:
                error_magnitude = s1
                return [(l, error_magnitude)]

    # Пробуем найти две ошибки (упрощенно)
    if s1 != 0 and s2 != 0 and s3 != 0 and s4 != 0:
        # Решаем систему уравнений для двух ошибок
        try:
            # σ₁ = (s₁s₃ + s₂²) / (s₁s₂ + s₃)
            numerator1 = gf.add(gf.mul(s1, s3), gf.mul(s2, s2))
            denominator1 = gf.add(gf.mul(s1, s2), s3)

            if denominator1 != 0:
                sigma1 = gf.div(numerator1, denominator1)

                # σ₂ = (s₁s₄ + s₂s₃) / (s₁s₂ + s₃)
                numerator2 = gf.add(gf.mul(s1, s4), gf.mul(s2, s3))
                sigma2 = gf.div(numerator2, denominator1)

                # Находим корни многочлена локатора x² + σ₁x + σ₂
                errors = []
                for l in range(7):
                    alpha_l = gf.pow(gf.alpha, l)
                    value = gf.add(gf.add(gf.mul(alpha_l, alpha_l),
                                          gf.mul(sigma1, alpha_l)), sigma2)
                    if value == 0:
                        # Найден корень - позиция ошибки
                        errors.append(l)

                if len(errors) == 2:
                    # Находим величины ошибок (упрощенно)
                    l1, l2 = errors
                    alpha_l1 = gf.pow(gf.alpha, l1)
                    alpha_l2 = gf.pow(gf.alpha, l2)

                    # Решаем систему для величин ошибок
                    denominator_e = gf.add(gf.mul(alpha_l1, alpha_l2),
                                           gf.mul(alpha_l1, alpha_l1))
                    if denominator_e != 0:
                        e1 = gf.div(gf.add(s1, gf.mul(alpha_l2, s1)), denominator_e)
                        e2 = gf.add(s1, e1)

                        return [(l1, e1), (l2, e2)]
        except:
            pass

    return []  # не удалось исправить


def correct_errors(received, error_positions_magnitudes, gf):
    """Исправление ошибок в принятом слове"""
    corrected = received.copy()

    for pos, magnitude in error_positions_magnitudes:
        if 0 <= pos < len(corrected):
            corrected[pos] = gf.add(corrected[pos], magnitude)

    return corrected


def test_single_error(gf):
    """Тестирование исправления одиночной ошибки"""
    print("=== Исправление одиночной ошибки ===")

    # Исходное сообщение и кодовое слово
    message = [0b001, 0b001, 0b000]  # 1 + x
    codeword = [0b001, 0b110, 0b010, 0b100, 0b101, 0b111, 0b011]  # закодированное

    print(f"Исходное кодовое слово: {[format(c, '03b') for c in codeword]}")

    # Вносим одиночную ошибку
    corrupted = simulate_errors(codeword, [2], [0b001], gf)
    print(f"С ошибкой в позиции 2: {[format(c, '03b') for c in corrupted]}")

    # Вычисляем синдромы
    syndromes = compute_syndromes(corrupted, gf)
    print(f"Синдромы: {[format(s, '03b') for s in syndromes]}")

    # Находим и исправляем ошибки
    errors = berlekamp_massey(syndromes, gf)
    print(f"Найденные ошибки: {errors}")

    if errors:
        corrected = correct_errors(corrupted, errors, gf)
        print(f"После исправления: {[format(c, '03b') for c in corrected]}")
        print(f"Корректно исправлено: {corrected == codeword}")
    else:
        print("Не удалось исправить ошибки")


def test_double_error(gf):
    """Тестирование исправления двойной ошибки"""
    print("\n=== Исправление двойной ошибки ===")

    # Исходное кодовое слово
    codeword = [0b001, 0b110, 0b010, 0b100, 0b101, 0b111, 0b011]
    print(f"Исходное кодовое слово: {[format(c, '03b') for c in codeword]}")

    # Вносим две ошибки
    corrupted = simulate_errors(codeword, [1, 4], [0b010, 0b001], gf)
    print(f"С ошибками в позициях 1,4: {[format(c, '03b') for c in corrupted]}")

    # Вычисляем синдромы
    syndromes = compute_syndromes(corrupted, gf)
    print(f"Синдромы: {[format(s, '03b') for s in syndromes]}")

    # Находим и исправляем ошибки
    errors = berlekamp_massey(syndromes, gf)
    print(f"Найденные ошибки: {errors}")

    if errors:
        corrected = correct_errors(corrupted, errors, gf)
        print(f"После исправления: {[format(c, '03b') for c in corrected]}")
        print(f"Корректно исправлено: {corrected == codeword}")
    else:
        print("Не удалось исправить ошибки")


def error_correction_capability(gf):
    """Демонстрация корректирующей способности"""
    print("\n=== Корректирующая способность RS(7,3) ===")

    codeword = [0b001, 0b110, 0b010, 0b100, 0b101, 0b111, 0b011]

    # Тестируем разное количество ошибок
    for num_errors in range(1, 5):
        print(f"\n{num_errors} ошибка(ок):")

        # Создаем ошибки в первых num_errors позициях
        error_positions = list(range(num_errors))
        error_values = [0b001] * num_errors  # все ошибки величины 1

        corrupted = simulate_errors(codeword, error_positions, error_values, gf)
        syndromes = compute_syndromes(corrupted, gf)
        errors = berlekamp_massey(syndromes, gf)

        if errors:
            corrected = correct_errors(corrupted, errors, gf)
            success = corrected == codeword
            print(f"  Успешно исправлено: {success}")
        else:
            print("  Не удалось исправить")


if __name__ == "__main__":
    gf = GF8()
    test_single_error(gf)
    test_double_error(gf)
    error_correction_capability(gf)