InfTh/P2/main.py

import matplotlib.pyplot as plt
import numpy as np


# Linear Feedback Shift Register
class LFSR:
    def __init__(self, poly):
        # LSB -> MSB
        self.g = []
        self.reg = []

        '''
        poly = str(n, n-1, ..., 0) => g = [0, ..., n-1]
                   0, 1, ..., -1

        [-1:0:-1] = von(inkl.):bis(exkl.):Schritt => [Ende:Anfang[
        '''
        for ziffer in poly[-1:0:-1]:
            self.reg.append(0)
            self.g.append(int(ziffer))

    def get_reg_as_string(self):
        reg_string = ""

        for i in self.reg:
            reg_string += str(i)  # LSB -> MSB

        return reg_string

    def shift(self, s_i):
        reg_old = self.reg.copy()  # alter Zustand, um überschreibungen zu vermeiden

        feedback = reg_old[-1] ^ int(s_i)

        for i, value in enumerate(self.g):
            if i == 0:
                self.reg[i] = feedback
            else:
                if value == 1:
                    self.reg[i] = reg_old[i - 1] ^ feedback
                else:
                    self.reg[i] = reg_old[i - 1]


def CRC_Parity(s, g):
    schiebe_reg = LFSR(g)

    # LSB -> MSB => MSB -> LSB
    for s_i in s[::-1]:
        schiebe_reg.shift(s_i)

    return schiebe_reg.get_reg_as_string()


def channel_bsc(p, n):
    errors = ""

    for i in range(n):
        errors += "1" if np.random.random() < p else "0"

    return errors


def send_channel(p, codeword, error_pattern):
    received = ""

    for j in range(len(codeword)):
        bit1 = int(codeword[j])
        bit2 = int(error_pattern[j])
        received += str(bit1 ^ bit2)

    return received


def p_k_Fehler(p):
    # P_k = (nCk) * p^k * (1-p)^(n-k)
    n = 1000
    p_k = []
    k_values = list(range(1, n + 1))

    for k in k_values:
        nCk = 1
        for i in range(1, k + 1, 1):
            nCk = nCk * ((n + 1 - i) / i)

        # p_k = (nCk) * p^k * (1-p)^(n-k)
        p_k.append(nCk * pow(p, k) * pow((1 - p), (n - k)))

    plt.figure(figsize=(12, 8))
    plt.plot(k_values, p_k)  # plot(x,y)

    # Achsenbeschriftung
    plt.xlabel('k (Anzahl Fehler)', fontsize=12)
    plt.ylabel('p_k', fontsize=12)
    plt.title(f'Fehlerwahrscheinlichkeiten BSC Kanal (p={p}, n={n})', fontsize=14)

    # Grid
    plt.grid(True, alpha=0.3)

    # Zeige Plot
    plt.tight_layout()  # Besseres Layout
    plt.show()


def optimal_blocksize(p, word, poly):
    crc_bits = len(poly) - 1
    n = len(word)

    best_datasize = float('inf')
    best_blocksize = 0

    for i in range(10):
        block_size_i = 2 ** i
        if block_size_i < n:
            blocks = n / block_size_i
            codeword_size = block_size_i + crc_bits
            p_succesful = (1 - p) ** codeword_size
            block_avrg_reps = 1 / p_succesful
            block_avrg_datasize = codeword_size * block_avrg_reps

            total_avrg_datasize = block_avrg_datasize * blocks
            if total_avrg_datasize < best_datasize:
                best_datasize = total_avrg_datasize
                best_blocksize = block_size_i

    return best_blocksize


def generate_random_binary(n):
    bin_string = ""

    for i in range(n):
        bin_string += "1" if np.random.random() < 0.5 else "0"

    return bin_string


def split_into_blocks(word, block_size):
    blocks = []

    for i in range(0, len(word), block_size):
        block = word[i:i + block_size]
        blocks.append(block)

    return blocks


def main():
    p = 0.1
    n = 1000

    detected_blocks = 0
    repeats = 0
    total_errors = 0
    total_transmited_data = 0

    # LSB -> MSB
    # s = "110011101100101"
    word = generate_random_binary(n)

    # MSB -> LSB
    poly = "100101"

    blocksize = optimal_blocksize(p, word, poly)

    blocks = split_into_blocks(word, blocksize)

    p_k_Fehler(p)

    for i, block in enumerate(blocks):
        # CRC-Codierung
        crc_bits = CRC_Parity(block, poly)
        codeword = crc_bits + block

        # BSC-Kanal
        error_pattern = channel_bsc(p, len(codeword))
        received = send_channel(p, codeword, error_pattern)

        # Fehlerprüfung
        check = CRC_Parity(received, poly)

        print(f"==========BLOCK {i + 1}==========")
        print(f"   Codewort: {codeword}")
        print(f" Fehlerwort: {error_pattern}")
        print(f"  Empfangen: {received}")

        detected_blocks += 1 if "1" in check else 0
        total_transmited_data += len(codeword)
        repeats += 1

        '''
        if "1" in check:
        print("                      ❌ Fehler  ")
        total_errors += error_pattern.count("1")
        else:
        print("                      ✅ Erfolgreich")

        '''


        '''
        Version in der fehlerhafte Übertragungen so lange wiederholt werden, bis sie fehlerfrei sind
        '''


        while "1" in check:
            print("                      ❌ Fehler  ")
            total_errors += error_pattern.count("1")

            # erneute Übertragung
            repeats += 1
            total_transmited_data += len(codeword)
            error_pattern = channel_bsc(p, len(codeword))
            received = send_channel(p, codeword, error_pattern)
            check = CRC_Parity(received, poly)
            print(f"  Empfangen: {received}")

        print("                      ✅ Erfolgreich \n")




    # Ende
    print("============ ERGEBNISSE ============")
    print(f"ursprüngliche Datenmenge: {n} Bits")
    print(f"                       p: {p * 100} %")
    print(f"       generator Polynom: {poly}")
    print(f"              Blockgröße: {blocksize}")
    print(f"             Blockanzahl: {len(blocks)}")
    print(f"  übertragene Datenmenge: {total_transmited_data} Bit")
    print(f"      fehlerfreie Blöcke: {len(blocks) - detected_blocks} = {((len(blocks) - detected_blocks) / len(blocks) * 100):.2f} %")
    print(f"          Wiederholungen: {repeats}, ca. {(repeats / len(blocks)):.1f} p.Bl.")
    print(f"        fehlerhafte Bits: {total_errors} Bit = {(total_errors / total_transmited_data * 100):.2f}%")


if __name__ == '__main__':
    main()