task3_2.py - master - ku11ch/Lab_3

task3_2.py
144 строки6 KB
ku11ch
upload files
14 окт 2025, 10:54
14 окт 2025, 10:5424ce3ca
# Код с постоянным весом

import itertools
import random
import math


class ConstantWeightCode:
    @staticmethod
    def generate_codewords(n, k):
        if k > n or k < 0:
            return []

        # Все комбинации позиций для k единиц
        return list(itertools.combinations(range(n), k))

    @staticmethod
    def codeword_to_binary(codeword, n):
        binary = 0
        for pos in codeword:
            binary |= (1 << (n - 1 - pos))
        return binary

    @staticmethod
    def binary_to_codeword(binary, n):
        positions = []
        for i in range(n):
            if binary & (1 << (n - 1 - i)):
                positions.append(i)
        return tuple(positions)

    @staticmethod
    def is_valid_codeword(binary, n, k):
        # Проверка длины
        if binary.bit_length() > n:
            return False

        # Проверка веса
        ones_count = bin(binary).count('1')
        return ones_count == k

    @staticmethod
    def calculate_detection_probability(p, n, k, num_tests=1000):
        # Генерируем все возможные кодовые слова
        codewords = ConstantWeightCode.generate_codewords(n, k)
        if not codewords:
            return 0.0

        detected_errors = 0
        total_errors = 0

        for _ in range(num_tests):
            # Выбираем случайное кодовое слово
            original_codeword = random.choice(codewords)
            original_binary = ConstantWeightCode.codeword_to_binary(original_codeword, n)

            # Вносим ошибки
            corrupted_binary = original_binary
            error_occurred = False

            for i in range(n):
                if random.random() < p:
                    corrupted_binary ^= (1 << (n - 1 - i))
                    error_occurred = True

            if error_occurred:
                total_errors += 1
                # Проверяем, осталось ли слово допустимым
                if not ConstantWeightCode.is_valid_codeword(corrupted_binary, n, k):
                    detected_errors += 1

        return detected_errors / total_errors if total_errors > 0 else 1.0

    @staticmethod
    def get_code_parameters(n, k):
        codewords = ConstantWeightCode.generate_codewords(n, k)
        total_possible = 2 ** n
        actual_codes = len(codewords)

        return {
            'total_possible_combinations': total_possible,
            'actual_codewords': actual_codes,
            'code_rate': math.log2(actual_codes) / n if actual_codes > 0 else 0,
            'redundancy': 1 - (math.log2(actual_codes) / n) if actual_codes > 0 else 1
        }


def demonstrate_constant_weight():
    """Демонстрация работы кода с постоянным весом"""
    print("=== Код с постоянным весом ===")

    # Параметры кода
    n = 6  # Длина кодового слова
    k = 3  # Вес (количество единиц)

    print(f"Параметры кода: длина n={n}, вес k={k}")

    # Генерация кодовых слов
    codewords = ConstantWeightCode.generate_codewords(n, k)
    print(f"\nВсего кодовых слов: {len(codewords)}")

    # Вывод первых 10 кодовых слов
    print("Первые 10 кодовых слов:")
    for i, cw in enumerate(codewords[:10]):
        binary = ConstantWeightCode.codeword_to_binary(cw, n)
        print(f"  {cw} -> {format(binary, f'0{n}b')}")

    # Проверка корректности
    test_binary = ConstantWeightCode.codeword_to_binary(codewords[0], n)
    print(f"\nПроверка корректности кодового слова {format(test_binary, f'0{n}b')}:")
    print(f"  Корректно: {ConstantWeightCode.is_valid_codeword(test_binary, n, k)}")

    # Внесение ошибки и проверка
    corrupted = test_binary ^ (1 << (n - 1))  # Инвертируем первый бит
    print(f"После внесения ошибки: {format(corrupted, f'0{n}b')}")
    print(f"  Корректно: {ConstantWeightCode.is_valid_codeword(corrupted, n, k)}")

    # Параметры кода
    params = ConstantWeightCode.get_code_parameters(n, k)
    print(f"\nХарактеристики кода:")
    for key, value in params.items():
        print(f"  {key}: {value:.4f}")

    # Коэффициент обнаружения ошибок
    p_error = 0.1
    detection_prob = ConstantWeightCode.calculate_detection_probability(p_error, n, k, 2000)
    theoretical_prob = 1 - (1 - p_error) ** k

    print(f"\nКоэффициент обнаружения ошибок (p={p_error}):")
    print(f"  Теоретический: {theoretical_prob:.4f}")
    print(f"  Экспериментальный: {detection_prob:.4f}")

    # Исследование влияния параметров
    print("\nИсследование влияния параметров на помехоустойчивость:")
    test_cases = [(4, 2), (5, 2), (6, 3), (7, 3)]

    for test_n, test_k in test_cases:
        prob = ConstantWeightCode.calculate_detection_probability(0.1, test_n, test_k, 1000)
        params = ConstantWeightCode.get_code_parameters(test_n, test_k)
        print(f"n={test_n}, k={test_k}: обнаружение={prob:.4f}, избыточность={params['redundancy']:.4f}")


if __name__ == "__main__":
    demonstrate_constant_weight()