task3_5.py - master - ku11ch/Lab_3

task3_5.py
155 строк6 KB
ku11ch
upload files
14 окт 2025, 10:54
14 окт 2025, 10:5424ce3ca
# Код Грея

import random


class GrayCode:
    @staticmethod
    def binary_to_gray(n):
        return n ^ (n >> 1)

    @staticmethod
    def gray_to_binary(gray):
        binary = gray
        while gray > 0:
            gray >>= 1
            binary ^= gray
        return binary

    @staticmethod
    def generate_gray_sequence(n_bits):
        return [GrayCode.binary_to_gray(i) for i in range(2 ** n_bits)]

    @staticmethod
    def hamming_distance(a, b):
        return bin(a ^ b).count('1')

    @staticmethod
    def introduce_error(gray_code, error_probability=0.1):
        corrupted = gray_code
        bits = gray_code.bit_length() if gray_code > 0 else 1

        for i in range(bits):
            if random.random() < error_probability:
                corrupted ^= (1 << i)

        return corrupted

    @staticmethod
    def calculate_error_propagation(original_value, corrupted_gray, n_bits):
        # Декодируем corrupted код
        decoded_binary = GrayCode.gray_to_binary(corrupted_gray)

        # Оригинальное значение в коде Грея
        original_gray = GrayCode.binary_to_gray(original_value)

        # Ошибка в коде Грея
        gray_error = GrayCode.hamming_distance(original_gray, corrupted_gray)

        # Ошибка после декодирования
        binary_error = GrayCode.hamming_distance(original_value, decoded_binary)

        return {
            'original_value': original_value,
            'original_gray': original_gray,
            'corrupted_gray': corrupted_gray,
            'decoded_binary': decoded_binary,
            'gray_error_bits': gray_error,
            'binary_error_bits': binary_error,
            'error_propagation': binary_error - gray_error
        }

    @staticmethod
    def calculate_detection_probability(n_bits, error_probability=0.1, num_tests=1000):
        gray_sequence = GrayCode.generate_gray_sequence(n_bits)
        detected_errors = 0
        total_tests = 0

        for _ in range(num_tests):
            # Выбираем случайное значение
            original_value = random.randint(0, 2 ** n_bits - 1)
            original_gray = GrayCode.binary_to_gray(original_value)

            # Вносим ошибки
            corrupted_gray = GrayCode.introduce_error(original_gray, error_probability)

            # Декодируем
            decoded_binary = GrayCode.gray_to_binary(corrupted_gray)

            # Проверяем, изменилось ли значение
            if decoded_binary != original_value:
                detected_errors += 1

            total_tests += 1

        return detected_errors / total_tests if total_tests > 0 else 0.0


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

    n_bits = 4
    print(f"Последовательность кодов Грея для {n_bits} бит:")

    gray_sequence = GrayCode.generate_gray_sequence(n_bits)
    for i, gray in enumerate(gray_sequence):
        binary = GrayCode.gray_to_binary(gray)
        print(f"  Десятичное: {i:2d} -> Бинарное: {binary:04b} -> Грей: {gray:04b}")

    # Демонстрация свойства минимальных изменений
    print(f"\nСвойство минимальных изменений (соседние значения):")
    for i in range(1, len(gray_sequence)):
        prev_gray = gray_sequence[i - 1]
        curr_gray = gray_sequence[i]
        hamming_dist = GrayCode.hamming_distance(prev_gray, curr_gray)
        print(f"  {prev_gray:04b} -> {curr_gray:04b}: расстояние Хэмминга = {hamming_dist}")

    # Тестирование преобразований
    test_value = 0b1101  # 13
    gray_code = GrayCode.binary_to_gray(test_value)
    back_to_binary = GrayCode.gray_to_binary(gray_code)

    print(f"\nТестирование преобразований:")
    print(f"Исходное бинарное: {test_value:04b} ({test_value})")
    print(f"Код Грея: {gray_code:04b} ({gray_code})")
    print(f"Обратное преобразование: {back_to_binary:04b} ({back_to_binary})")
    print(f"Преобразование корректно: {test_value == back_to_binary}")

    # Анализ распространения ошибок
    print(f"\nАнализ распространения ошибок:")
    test_cases = [
        (5, 0b0001),  # маленькая ошибка
        (5, 0b1000),  # большая ошибка
    ]

    for original, error_pattern in test_cases:
        original_gray = GrayCode.binary_to_gray(original)
        corrupted_gray = original_gray ^ error_pattern

        error_info = GrayCode.calculate_error_propagation(original, corrupted_gray, n_bits)

        print(f"Оригинал: {original:04b}, ошибка: {error_pattern:04b}")
        print(f"  Ошибка в Грее: {error_info['gray_error_bits']} бит")
        print(f"  Ошибка после декодирования: {error_info['binary_error_bits']} бит")
        print(f"  Распространение ошибки: {error_info['error_propagation']}")

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

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

    # Сравнение с обычным бинарным кодом
    print(f"\nСравнение с обычным бинарным кодом:")
    print("Преимущества кода Грея:")
    print("  - Минимальные изменения между соседними значениями")
    print("  - Уменьшение ошибок при переходе между состояниями")
    print("  - Широкое применение в энкодерах и измерительных системах")


if __name__ == "__main__":
    demonstrate_gray_code()