mB/nB 인코딩에서 사용할 수 있는 codeword 개수

mB/nB 인코딩(일반적으로 n = m + 1)에서는 dataword를 codeword로 인코딩할 때 연속적으로 등장하는 0의 개수가 m 미만이 되는 것을 목표한다. (self-synchronization 위함)

4B/5B 인코딩에서 사용할 수 있는 codeward를 구하는 방식으로, 앞의 2bit와 뒤의 3bit에 1이 최소한 하나 있어야 한다고 배웠다. 그러면 codeword 내부에서도 연속된 0이 4개 이상 등장하지 않고, 두 codeword를 이어붙일 때 하나의 codeword의 뒷부분과 다른 것의 앞부분이 concatenate 됨에 따라 발생하는 연속되는 0의 개수도 4개 이상이 되지 않는다. (ex. 01100을 두 개 이어 붙이면 0110001100이고 가운데 연속적으로 생기는 0이 3개이므로 괜찮음)

따라서 가능한 codeword의 개수를 2^5 - 2^2 - 2^3 + 1 = 21로 구하면 된다.

7B/8B 인코딩은?
앞의 4개, 뒤의 4개에 최소 한 개의 1이 있도록 할 수도 있고 (ex. 최악의 상황은 00011000이고, 이걸 두 번 이어붙여도 연속한 0의 개수가 6개이다)
앞의 3개, 뒤의 5개로 나누어 똑같이 할 수도 있다 (ex. 00110000).

정말로 둘 다 가능한 건지 코드 짜서 확인해봤는데

 

import itertools

M = 7
N = M + 1
DIVIDING_IDX = 4

print(f'{M}B/{N}B')

combinations = list(itertools.product([0, 1], repeat=N))
codewords = [list(comb) for comb in combinations if 1 in comb[:DIVIDING_IDX] and 1 in comb[DIVIDING_IDX:]]
print(f'Number of codewords: {len(codewords)}')

for cw1 in codewords:
    for cw2 in codewords:
        concatenated = cw1 + cw2
        consecutive_zeros = 0
        max_consecutive_zeros = 0

        for num in concatenated:
            if num == 0:
                consecutive_zeros += 1
                max_consecutive_zeros = max(max_consecutive_zeros, consecutive_zeros)
            else:
                consecutive_zeros = 0

        if not max_consecutive_zeros < M:
            print(cw1, cw2)

 

잘못된 조합이 있으면 출력하도록 했는데 아무것도 나오지 않았다.
DIVIDING_IDX를 1~4까지 시도해봐도 모두 괜찮다.

그런데 이렇게 두 개로 나눌 때 각각의 크기가 커지면, 사용할 수 없는 경우의 수가 많아지기 때문에, 전체 가능한 codeword 개수가 줄어들게 된다.
예를 들어 4개와 4개의 조합으로 나누면 2^8 - 2^4 - 2^4 + 1 = 225개 사용할 수 있는데, 3개와 5개의 조합으로는 2^8 - 2^3 - 2^5 + 1 = 217개로 줄어든다.

이게 크리티컬 할 수도 있는데, 예를 들어 4B/5B의 경우 1개와 4개의 조합으로 나누어 생각한다면 가능한 codeword 개수가 2^5 - 2^1 - 2^4 + 1 = 15개이고, 이걸로 2^m = 16가지의 dataword를 인코딩할 수 없게 된다! (당연함 2^n - 2^1 - 2^(n-1) + 1 = 2^(n-1) - 1 인데 n - 1 = m이니까)

그러므로 그냥 두 sub codeword 간의 차이가 최소화되도록 나누는 게 가장 좋다.
깨달아버린 것이야.
아주 신기가 방기다.

다들 시험 잘 보세요!

 

 

 

 

https://blog.naver.com/mini_gb/223421973641

mB/nB 인코딩에서 사용할 수 있는 codeword 개수