KR970004256B1

KR970004256B1 - 순환코드를 이용한 프레임/버스트 동기 및 에러 검출장치

Info

Publication number: KR970004256B1
Application number: KR1019940015086A
Authority: KR
Inventors: 최양호
Original assignee: 한국전기통신공사; 조백제
Priority date: 1994-06-29
Filing date: 1994-06-29
Publication date: 1997-03-26
Also published as: KR960001996A; US5745510A

Abstract

내용 없음.

Description

순환코드를 이용한 프레임/버스트 동기 및 에러 검출장치

제1도는 수신블럭에서 머리, 중간, 꼬리블럭의 위치를 도시한 도면.

제2도는 본 발명에 의한 동기/에러 검출장치의 블럭 구성도.

제3도는 본 발명에 의한 동기/에러 검출로직부의 실시예도.

제4도는 본 발명에 의한 동기/꼬리 신드롬 계산부의 실시예도.

*도면의 주요 부분에 대한 부호의 설명*

20 : 지연부21 : 동기/에러 검출로직부

22 : 디코더23 : 메세지 블럭 출력부

24 : 마커25 : 수신블럭

26 : 신드롬210 : 머리/꼬리 신드롬 계산부

211 : 카운터212 : 슬립 레지스터

213 : 에러 검출부2100 : 제1 쉬프트 레지스터

2101 : 제2 쉬프트 레지스터

본 발명은 순환코드(cyclic code)를 이용하여 프레임/버스트 동기 및 채널에러를 효율적으로 검출하는 장치에 관한 것이다.

순환코드는 보통 코드워드(code word) 앞 부분에 메세지 블럭을 두고 그 다음에 CRC (Cyclic Redundan-cy code) 비트를 두는 조직 코드(systematic code)를 많이 이용한다. 상기 CRC 비트는 코드워드의 신드롬을 0으로 만들어 주며, 순환코드의 채널에러 발생 여부는 신드롬을 계산하면 알 수 있다.

코드워드의 일부 비트를 반전시킨 코셋코드를 이용하면 채널에러 검출뿐만 아니라 버스트 동기의 검출도 가능하며, 순환코드를 이용한 동기의 검출은 버스트가 어떤 주어진 검출구간 내에 도착할 때에만 가능하다. 다시 말하면 전송된 순환코드가 채널에러 없이 수신되고 코드의 첫번째 비트가 검출범위 내에 있다면 정확하게 버스트 동기를 검출할 수 있으나 이 검출범위를 벗어나면 채널에러가 없더라도 정확히 동기를 검출할 수 없게 된다.

상기에서 이용하는 순환코드가 코드워드의 길이가 n이고 메세지의 길이가 k인 (n, k) 순환코드라 하면 검출범위는 이론적으로 최대 n-k 비트가 된다. (이하, 설명의 편의상 n-k는 짝수라 가정한다.)

종래의 방법에서는 보통 코드워드의 첫번째 비트와 마지막 비트를 마킹시켜 전송하며, 검출영역의 중앙을 기준시점으로 하여 ± d(=(n-k-2)/2) 비트슬립을 검출할 수 있으므로 전체 동기 검출범위는 상기의 이론적 최대치보다 1 비트 작은 n-k-1 비트가 된다. 여기서 +, -는 슬립 방향을 나타내는 부호로서 +은 버스트의 도착시점이 기준시점보다 빠름을, 즉 오른쪽 방향으로의 비트슬립을 의미하며, -는 버스트의 도착시점이 기준시점보다 늦음을, 즉 왼쪽 방향으로의 비트슬립을 의미한다.

종래의 방법에서는 먼저 비트슬립을 검출하고 검출된 비트슬립으로부터 버스트를 재구성하여 에러검사를 행하고, 각각의 과정에서 CRC 디코팅을 필요로 한다.

상기의 비트슬립은 n개의 비트로 구성되는 블럭을 처리하여 검출하는데, 이를 상세히 설명하면 처리할 블럭의 첫번째 비트(기준시점에 위치한 비트)와 n번째 비트를 마킹하여 앞의 d+1개의 비트를 회전쉬프트한 다음 CRC 디코팅을 통해 신드롬을 구하고, 구해진 신드롬이 [도표 1]의 동기 신드롬 패턴 중의 하나와 일치하면 비트슬립을 알 수 있으며 일치하지 않는다면 동기검출은 실패한 것으로 처리된다.

[도표 1]에서 X는 0이거나 1이거나를 상관하지 않음을 의미한다. 하위 d+1 비트의 동기패턴은 상기에서 회전쉬프트한 d+1개의 비트로부터 형성된 패턴이며, 상위 또는 하위 비트패턴으로부터 슬립방향을 알 수 있다. 즉, 상기 d+1개의 비트가 00···01의 패턴을 가진다면 왼쪽 방향으로, 하위 d+1개의 비트가 10···00의 패턴을 가진다면 오른쪽 방향으로 비트슬립이 발생했음을 나타낸다. 상기에서 발생한 비트슬립의 크기는 나머지 d+1 비트 패턴에서 처음 또는 마지막에 나타난 1의 위치로부터 구해진다.

[도표 1]

종래의 방식에 있어서는 앞에서 설명한 바와 같이, 두번의 마킹 및 CRC 디코팅을 필요로 하므로 시스템 구성이 복잡해지고 처리시간이 길어지는 문제가 있었다.

따라서, 본 발명에서는 상기 종래 기술의 문제를 해결하기 위하여, 한번의 CRC 디코팅 과정으로 프레임/버스트의 동기 및 에러를 검출하는 장치를 제공하는데에 그 목적이 있다.

이하, 본 발명에 의한 동기 및 에러검출 원리를 설명하기로 한다.

우선, 비트 시퀀스 ···r_-1r₀r₁··· 이 수신될 때에 2n-k 비트로 구성되는 수신블럭(R)을 아래와 같이 세개의 블럭으로 나누어 생각하기로 한다.

R=(r_-(n-k), r_-(n-k-1), ···, r_-1, r₀, ···, r_k-1, r_k, ···, r_n-2, r_n-1)

=(γ_h, γ_m, γ_t)------ (1)

상기에서 γ_h는 수신블럭(R)에서 앞의 n-k 비트로, γ_m은 다음 k 비트로, γ_t는 뒤의 n-k 비트로 구성되는 블럭으로;

γ_h=(r_-(n-k), r_-(n-k-1), ···, r_-1)

γ_m=(r₀, r₁, ···, r_k-1)------ (2)

γ_t=(r_k, r_k-1, ···, r_n-2, r_n-1)

이며, 편의상 γ_h를 머리블럭, γ_m을 중간블럭, γ_t를 꼬리블럭으로 정의한다.

제1도는 수신블럭에서 각 블럭 및 기준시점의 위치를 도시한 것으로, 기준시점은 중간블럭의 첫번째 비트위치로 정하였다.

전송 버스트의 도착시점에 n-k-1 비트 타임 이하의 모호암이 있다고 하면 항상 전송 버스트를 수신블럭(R) 내에 있게 할 수 있다. 따라서 가장 빨리 도착하는 경우 전송 버스트의 첫번째 비트와 마지막 비트는 각각 r_-(n-k-1)과 r_k에 위치하게 된다. 다시 말하면 수신블럭을 상기 식 (2)와 같이 분할할 때에 항상 전송 버스트의 첫번째 비트는 γ_h에, 마지막 비트는 γ_t에 있게 된다.

전송에러가 없는 경우라 하고, 이때 전송 버스트의 첫번째 비트가 γ_h의 n-k+1-j번째 비트에 해당한다면;

γ_h=(r_-(n-k), ···, r_-(j+1), /c₀, c₁, ···, c_j-1)

γ_m=(c_j, ···, c_k-1+j)------ (3)

γ_t=(c_k+j, ···, c_n-2, /c_n-1, r_n-j, ···, r_n-1)

와 같이 주어진다. 여기서 (/c₀, c₁, ···, /c_n-1)은 전송된 토셋코드이다.

중간블럭에 꼬리블럭을 첨가하여 구성한 n 비트블럭 (γ_m, γ_t)에 대한 신드롬은 각각 [도표 2]에서 항상 비트슬립이 +값을 갖는 것은 앞에서 정의한 바와 같이 중간블럭의 첫번째 비트를 기준시점으로 했기 때문이다. 전송 버스트의 첫번째 비트는 항상 머리블럭에 존재하여 중간블럭의 첫번째 비트보다 최소 1 비트이상 왼쪽에 위치하게 된다.

수신블럭이 상기 식 (3)과 같이 주어졌다면 꼬리, 머리 신드롬은 [도표 2]에서 S=j일 때의 패턴과 같다. 이때 꼬리 신드롬은 최상위 비트(MSB)로부터 n-k-j번째에 처음 1의 비트가 나타나고 머리 신드롬은 최하위 비트(LSB)로부터 j번째에 처음 1의 비트가 나타나므로, 머리 또는 꼬리 신드롬에서 처음으로 나타나는 1의 비트 위치를 찾으면 비트슬립을 알 수 있게 되며, 처음으로 나타나는 1의 비트는 코드워드의 마킹에 기인한다.

만약 어떤 수신블럭에 대한 머리, 꼬리 신드롬이 [도표 2]의 S=j일 때의 패턴과 같이 주어졌다면 이 수신블럭의 중간블럭에서 j 비트 만큼 왼쪽으로 쉬프트한 위치로부터 구성한 n 비트 블럭은 항상 코셋코드임을 알 수 있다.

결론적으로 머리, 꼬리 신드롬을 구하면 비트슬립 뿐만 아니라 채널에러 존재 여부도 알 수 있게 된다.

상기한 사실을 이용하여 다음과 같은 과정을 통해 버스트 동기 및 에러를 검출할 수 있다.

제1 단계로, 중간블럭 γ_m에 n-k개의 0 비트를 첨가하여 구성된 n 비트의 블럭 γ_s;

γ_s=(γ_m, 0, 0, ···, 0)------ (4)

를 CRC 디코딩하여 n-k 비트의 나머지 γ_R를 구한다.

제2단계로, 나머지에 각각 γ_h와 γ_t를 더하여 머리 신드롬 패턴 S_h와 꼬리 신드롬 패턴 S_t를 구한다. 즉;

S_h=γ_h+γ_R

S_t=γ_t+γ_R------ (5)

이며, 상기의 +는 익스클루시브-오아(exclusive-OR) 계산을 의미한다.

제3단계로, 상기에서 구한 머리 신드롬, 꼬리 신드롬이 동기 신드롬 패턴과 일치하는지를 조사하여 버스트 동기 및 에러를 검출한다.

[도표 2]

본 발명에서는 한번의 CRC 디코딩으로 꼬리 신드롬과 머리 신드롬을 구하여 비트슬립 및 코드워드에서의 에러를 검출한다. 다시 말하면 꼬리 신드롬, 머리 신드롬 중의 하나로부터 비트슬립을 알 수 있으며, 다른 하나의 신드롬으로부터 코드워드의 에러 여부가 검출된다고 볼 수 있다.

상기 [도표 2]를 보면 꼬리 신드롬에서 0 또는 1로 규정되어 있지 않은 X 비트 위치에 대응하는 머리 신드롬의 비트패턴은 규정되어 있고 반대의 경우도 마찬가지로 머리 신드롬에서 규정되지 않은 비트는 꼬리 신드롬에서는 규정되어 있다. 따라서, 두 신드롬에서 X로 표시된 비트를 빼고 합쳐서 하나의 신드롬으로 만들 수 있다. 예를 들어 S=2인 경우 합친 신드롬은 0000 … 00110의 패턴을 가진다. S=j일 때 합친 신드롬 패턴은 뒤에서 j번째와 j+1번째만 1 비트를 가지며, 이는 전송 버스트의 앞의 j 비트를 회전쉬프트한 블럭에 대한 신드롬과 일치한다.

제2도는 본 발명에 의한 동기/에러 검출장치의 실시예도로서, 수신블럭(25)을 지연시키는 지연부(20)와, 동기 및 에러를 검출하는 동기/에러 검출로직부(21)와, CRC 디코딩을 수행하는 디코더(22)와 메세지 블럭 출력부(23)와, 마킹된 메세지 비트를 반전시키는 마커(24)로 구성된다.

제3도는 본 발명에 의한 동기/에러 검출로직부(21)의 실시예를 도시한 것으로, 머리/꼬리 신드롬 계산부(210)와, 카운터(211)와, 슬립 레지스터(212)와, 에러 검출부(213)로 구성되어 있다.

제4도는 제3도의 머리/꼬리 신드롬 계산부(210)에 대한 실시예로서, 제1 쉬프트 레지스터(2100)와, 제2 쉬프트 레지스터(2101)로 구성되어 있다.

이하, 상기 제2도 내지 제4도를 참조하여 그 동작 과정을 설명하기로 한다. 설명에서 n-k 비트 중의 최상위 비트는 쉬프트 레지스터의 왼쪽, 최하위 비트는 오른쪽에 저장되어 있는 것으로 가정한다.

지연부(20)로 수신된 블럭(25)은 동기/에러 검출로직부(21)가 동기를 검출할 때까지 충분히 지연되며, 수신블럭(25)중의 머리, 꼬리블럭은 동기/에러 검출로직부(21)의 제1 쉬프트 레지스터(2100), 제2 쉬프트 레지스터(2101)에 저장되고, 중간블럭에 해당되는 부분이 디코더(22)에 입력되기 시작하면 CRC 디코딩 동작이 수행된다.

중간블럭을 구성하고 있는 k개의 비트 모두가 디코더(22)에 입력되면 n-k개의 0 비트가 디코더(22)에 입력되고, 디코딩을 계속하여 모두 n개의 비트블럭에 대한 신드롬(26)을 구한다. 구해진 신드롬(26)은 동기/에러 검출로직부(21)의 머리/꼬리 신드롬 계산부(210)로 입력되어 제1 및 제2 쉬프트 레지스터(2100, 2101)에 저장된 꼬리블럭과 머리블럭과 각각 익스클루시브-오아되어 머리 신드롬과 꼬리 신드롬이 구해지며, 구한 결과는 두 레지스터(2100, 2101)에 각각 저장된다.

비트슬립의 검출을 위해 머리 신드롬이 저장되어 있는 제2 쉬프트 레지스터(2101)을 오른쪽으로 쉬프트시키면서 카운터(211)를 이용하여 머리 신드롬에서 최하위 비트로부터 연속되어 있는 0 비트의 갯수를 카운트한다. 제2 쉬프트 레지스터(2101)의 최하위 비트에서 처음 1이 발생하면 카운트를 멈추고 지금까지 카운트된 값을 슬립 레지스터(212)에 저장한다. 이때 슬립 레지스터(212)에 저장된 값은 [도표 2]의 비트 슬립값보다 1 작은 값이며, 상기 지연부(20)에서 지연되어 메세지 블럭 출력부(23)로 입력되는 수신블럭 중 메세지 블럭의 위치는 상기 슬립 레지스터(212)에 저장된 값에 의해 파악되어 메세지 블럭이 출력되고, 메세지 블럭의 첫번째 메세지 비트는 마커(24)에 의해 반전된다.

한편, 슬립 레지스터(212)에 카운트의 결과가 저장되면 제1 쉬프트 레지스터(2100)를 왼쪽으로 쉬프트시키면서 이 레지스터의 최상위 비트에서 1이 검출될 때까지 카운터(211)로 계속 카운트하여, 꼬리 신드롬의 최상위 비트로부터 연속된 0 비트의 갯수와 이미 구한 머리 신드롬에서 연속된 0 비트의 갯수를 더한 결과를 구한다. 에러 검출부(213)는 상기에서 구한 결과가 n-k-2와 같은지 비교하여 에러 존재 여부를 판정한다.

본 발명의 또다른 실시 방식에서는 버스트를 전송할 때 첫번째와 마지막 비트의 2 비트를 마킹하는 대신에 그중 1 비트만을 마킹함으로써 비트슬립 검출범위를 기존 방식보다 1 비트 확장하는 것이 가능하며(기존 방식에서는 1 비트만을 마킹시켜 전송하면 동기의 검출이 불가능하였다.), 이때의 검출범위는 이론적 최대치에 해당한다. 1 비트 마킹하여 전송할 때의 동기/에러 검출과정은 앞에서 설명한 2 비트 마킹에서의 검출과정과 동일하며 이때의 동기 신드롬 패턴은 [도표 3]과 같이 주어진다. [도표 3]은 마지막 비트(n번째 비트)를 마킹한 경우의 신드롬 패턴으로서 S=0일 때도 동기의 검출이 가능함을 알 수 있다.

1 비트 마킹 방식에서의 동기/에러 검출장치는 제2도에서 마커(24)가 없는 경우와 동일하며 동기/에러 검출로직부(21)의 구성은 제3도와 같으나 동작방법은 약간 다르다. 머리/꼬리 신드롬은 상기에서 설명한 바와 동일하게 계산되며, 머리/꼬리 신드롬의 계산이 끝나면 카운터(211)는 먼저 꼬리 신드롬의 최상위 비트부터 시작하여 연속해서 있는 0 비트의 갯수를 계산하고 그 결과를 슬립 레지스터(212)에 저장한다.

n-k-1에 저장된 값을 뺀 결과 [도표 3]에 표시된 비트슬립 값과 일치하게 된다. 슬립 레지스터(212)에 저장이 끝나면 머리 신드롬이 저장되어 있는 제2 쉬프트 레지스터(2101)를 오른쪽으로 쉬프트하면서 쉬프트 레지스터의 최하위 비트가 0이면 카운터를 계속 증가시키고, 카운터(211)가 n-k-1에 도달하거나 이 값에 도달하기 전에 최하위 비트가 1이 되면 카운트는 끝나게 된다. 카운트가 종료되면 에러 검출부(23)에서는 카운터 출력이 n-k-1이면 채널에러가 없는 것으로 판정하고 그 외에는 채널에러가 있는 것으로 판정한다.

[도표 3]

본 발명을 종래와 같이 첫번째 비트와 마지막 비트를 반전시킨 코셋 코드를 이용하여 동기 및 에러의 검출에 적용하면 단 한번의 디코딩을 한다는 점 외에 동기 신드롬 계산과정에서 비트의 반전이 필요없고 단지 메세지 블럭의 복원에만 필요하다.

또한, 본 발명에서는 코드워드의 마지막 한 비트만을 마킹함으로써 비트슬립 검출범위를 종전의 방식보다 1 비트 확장시킬 수 있고 이때, 메세지 복원 과정에서도 반전이 필요하지 않으므로 시스템을 더욱 간단하게 구성할 수 있는 효과가 있다.

Claims

(n,k) 순환코드를 이용하여 프레임/버스트 동기 및 채널에러를 검출하는 시스템에 있어서, 2n-k 비트로 구성되는 수신블럭을 수신순서에 따라 n-k 비트의 머리 블럭(γ_L), 다음 n 비트블럭(γ_s, γ_t)와 (γ_s, γ_L)에 따라 꼬리 신드롬과 머리 신드롬으로부터 동기 및 에러 존재여부를 식별하는 것을 특징으로 하는 동기 및 에러 검출장치.
제1항에 있어서, 상기의 수신블럭을 적절한 시간동안 지연시키는 지연부와, 상기 수신블럭 중의 중간블럭이 수신되기 시작하면 CRC 디코딩을 수행하여 중간블럭에 n-k개의 0 비트를 추가하여 구성한 n 비트 블럭에 대한 신드롬을 계산하는 디코더와, 상기 디코더에서 계산된 신드롬과 머리블럭과 꼬리블럭을 이용하여 비트슬립과 에러 존재 여부를 알아내는 동기/에러 검출로직부와, 검출된 비트슬립으로부터 수신블럭 중의 메세지 블럭을 출력하는 메세지 블럭 출력부를 포함하는 것을 특징으로 하는 동기 및 에러 검출장치.
제2항에 있어서, 상기 디코더에서 계산한 신드롬과 머리블럭, 꼬리블럭을 이용하여 머리 및 꼬리 신드롬을 구하는 머리/꼬리 신드롬 계산부와, 상기 머리/꼬리 신드롬 계산부에서 구해진 머리 신드롬과 꼬리 신드롬에서 연속된 0 비트를 카운트하는 카운터와, 동기 위치에 관한 정보를 카운터로부터 받아서 저장하는 슬립 레지스터와, 상기 카운터의 결과로부터 에러 발생 여부를 판정하는 에러 검출부를 포함하는 것을 특징으로 하는 동기 및 에러 검출장치.
제3항에 있어서, 상기 머리/꼬리 신드롬 계산부는, 수신블럭 중의 머리블럭과 꼬리블럭을 각각 레지스터에 저장하고, 각각의 레지스터 출력과 CRC 디코딩을 통해 계산한 신드롬을 익스클루시브-오아(exclusive-OR)함으로써 머리 신드롬과 꼬리 신드롬을 구하는 것을 특징으로 하는 동기 및 에러 검출장치.
제3항에 있어서, 머리 신드롬이 저장되어 있는 레지스터를 쉬프트하여 레지스터의 최하위 비트부터 연속되어 있는 0 비트를 카운트하여 동기 정보를 알아내고 계속해서 꼬리 신드롬이 저장되어 있는 레지스터를 쉬프트하여 레지스터의 최상위 비트부터 연속되어 있는 0 비트를 카운트하여 이로부터 에러발생 여부에 관한 정보를 추출하거나 꼬리 신드롬에 연속되어 있는 0 비트를 먼저 카운트하여 동기정보를 알아내고 계속해서 머리 신드롬에 연속되어 있는 0 비트 갯수를 카운트하여 이로부터 에러발생 여부에 관한 정보를 추출하는 것을 특징으로 하는 동기 및 에러 검출 장치.