[CDC] 9_Multi Bit CDC: Asynchronous FIFO (Full 판단, Pointer Jump)

Gray CDC한 Pointer를 비교하여 Empty, Full 판단을 정확하게 하는 것이 중요하다. Empty 판단은 직관적으로 두 포인터가 같을 때이다. CDC 처리만 잘 되었다면 문제가 발생하지 않는다. 이해하기 어렵지 않다. 문제는 Full 판단이다. Full 판단은 Synchronous FIFO와 조금 다르다.

 

Synchronous FIFO에서 Full 판단

DEPTH = 8
wr_ptr : 4비트 (MSB 포함)
rd_ptr : 4비트 (MSB 포함)

 

 

• 조건 wr_ptr == rd_ptr만으로 판단하면 문제가 생김:
  • wr_ptr == rd_ptr → Empty 또는 Full 중 어느 상태인지 구분 불가
• 그래서 wrap bit / MSB를 추가해서 Full과 Empty를 구분함:
  • Empty: 포인터 완전히 같음
  • Full: 주소는 같지만 wrap bit는 다름

full = (wr_addr == rd_addr) && (wr_MSB != rd_MSB)

 

 

 

• 주소가 같지만 wrap bit가 다르면 → FIFO가 가득 찬 상태
• wrap bit가 한 사이클 뒤집히면 다음 위치가 read 포인터와 겹치기 때문에 write를 멈춰야 함

 

 

Synchronous FIFO에서 Full 판단을 하기 위해 추가 1bit가 필요했다.

 

 

 

Asynchronous FIFO에서 Full 판단

Asynchronous FIFO에서도 마찬가지로 추가 1bit만 필요하다. 하지만, full 판단하는 공식이 다르다.

 

결론부터 말하자면, Synchronous FIFO는 포인터의 상위 1비트가 다르고 나머지가 같을 때 Full이지만, Asynchronous FIFO는 상위 2비트가 다르고 나머지가 같을 때 Full이다.

 

그 이유는 Synchronous FIFO는 Binray에서 포인터를 비교했지만 Asynchronous FIFO에서는 Gray Code에서 비교해야하기 때문이다.

 

Binary에서 Full을 판정할 때 우리가 비교한 것은 주소가 같고 바퀴만 다른 상태였다.

 

그런데 Gray 공간에서는

• 주소라는 개념이 더 이상 비트 단위로 명확하지 않다
• wrap이라는 개념도 단일 비트로 존재하지 않는다

즉, Binary의 'wrap bit 1개'는 Gray에서는 '상위 2비트 패턴'으로 퍼져 있다.

 

Binary Full 상태를 Gray 공간에서 정확히 재현하려면 그 패턴이 상위 2비트 반전으로 나타난다. Binary에서 Full이 되는 의미를 Gray 공간에서도 절대 깨뜨리지 않기 위해 그 의미가 우연히 상위 2비트 반전으로 나타날 뿐이다.

 

 

예시로 확인해보자.

 

Synchronous FIFO(Binaray 포인터 예시)

Binary wr_ptr	Binary rd_ptr	Full?	이유
0000	0000	No	FIFO 비어있음
0001	0000	No	공간 있음
0010	0000	No	공간 있음
0011	0000	No	공간 있음
0100	0000	No	공간 있음
0101	0000	No	공간 있음
0110	0000	No	공간 있음
0111	0000	No	아직 공간 있음, wrap bit 동일
1000	0000	Yes	write pointer wrap bit 반전 → rd_ptr와 같은 주소 → Full

 

 

Full은 write pointer가 read pointer보다 정확히 FIFO depth만큼 앞서 있을 때 발생한다.

 

wr_ptr와 rd_ptr의 주소는 같고 wrap bit(MSB)가 반대이면 Full이다. 즉, 주소 000부터 111까지 write하면 wrap bit가 1로 바뀌면서 다음 write가 rd_ptr와 같은 주소(000)가 되는 순간 Full 발생한다.

 

Asynchronous FIFO(Gray 포인터 예시)

Binary wr_ptr	Gray wr_ptr	Binary rd_ptr	Gray rd_ptr	Full?	이유
0000	0000	0000	0000	No	FIFO 비어있음
0001	0001	0000	0000	No	공간 있음
0010	0011	0000	0000	No	공간 있음
0011	0010	0000	0000	No	공간 있음
0100	0110	0000	0000	No	공간 있음
0101	0111	0000	0000	No	공간 있음
0110	0101	0000	0000	No	공간 있음
0111	0100	0000	0000	No	공간 있음
1000	1100	0000	0000	Yes	상위 2비트 반전 + 하위 주소 동일 → Full

 

Full 판단 시 상위 2비트 반전 + 하위 주소 비교하면, Binary 기준 Full 상태와 동일하게 매칭된다.

 

 

 

왜 Asynchronous FIFO에서 상위 2비트를 반전해서 Full을 판단할까? 그 이유는 Gray Code의 구조적 특성 때문이다.

Binary Counter는 한 바퀴(DEPTH) 를 모두 돈 뒤에야 wrap bit(MSB) 가 0→1로 단순하게 반전된다. 즉, Binary에서는 wrap 정보가 정확히 1비트에만 존재한다.

 

하지만 Gray Code는 다르다. Gray Code는 인접한 값 사이에서 오직 1비트만 바뀌도록 설계되어 있기 때문에, Binary에서의 wrap bit 1개라는 개념이 Gray 공간에서는 한 비트에 고정되어 있지 않다. 특히 포인터가 FIFO depth만큼 앞서는 순간(= Binary Full 상태)을 Gray Code로 변환하면, 그 한 바퀴 돌았다는 정보가 단일 MSB가 아니라 상위 2비트의 조합 패턴으로 나타난다.

 

또 알아두어야 할 점은 Full은 write pointer가 read pointer보다 정확히 FIFO depth만큼 앞서 있을 때 발생한다는 것이다. wr_ptr가 0000(0) → 1100(8)까지 이동해서 Full이 될 수도 있지만, 0100(7) → 1000(15)까지 이동해서 Full이 될 수도 있다.Full인 상태에서 더 Write할 수는 없으니 Memory의 Depth보다 더 많은 데이터를 쓸 수는 없다.

 

주소 변환 공식

Gray Code는 우리가 아는 주소처럼 순차적이지 않아서 직관성이 떨어진다. 그때는 아래의 공식을 사용하면 우리에게 익숙한 순차적으로 돌아가는 Pointer 주소를 알 수 있을 것이다.

 

 

 

위 공식을 사용하면 우리가 아는 주소처럼 Pointer를 사용할 수 있다. 위 공식을 굳이 안 쓰고, Gray → Binary로 변환된 Pointer를 사용해도 문제없다.

 

 

Pointer Jump

https://rimeestore.tistory.com/entry/CDC-5Multi-Bit-CDC-Gray-Code

[CDC] 5_Multi Bit CDC: Gray Code

 

dst_bin이 중간 값을 skip

 

멀티 비트 Gray Code CDC에서는 수신 도메인의 클럭 속도가 송신 도메인보다 매우 느릴 경우, 송신 도메인에서 포인터가 여러 번 증가했더라도 수신 도메인에서는 그 중간 값들을 모두 관측하지 못하고 한 번에 다음 값으로 이동하는 현상이 발생할 수 있다.

 

// Write Pointer
0000 → 0001 → 0010 → 0011 → 0100 → 0101

// Read Pointer
0100  → (다음 샘플) → 0101

 

이처럼 중간 포인터 값들을 전혀 보지 못하고 건너뛰는 경우가 발생할 수 있다.

 

그러나 이는 Async FIFO 동작에서 전혀 문제가 되지 않는다. Async FIFO에서 중요한 것은 모든 포인터 값을 순서대로 관측하는 것이 아니라, 포인터가 단조 증가한다는 사실이 보장되는 것이다. 즉, 중간 값을 놓치더라도 과거 값으로 되돌아가지 않기만 하면 된다.

 

Gray Code의 특성상 수신 도메인은 포인터의 이전 값 또는 이후 값 중 하나로만 수렴하며, 깨진 조합의 값은 발생하지 않는다. 이로 인해 수신 도메인이 관측하는 포인터 값은 “여기까지는 write가 완료되었다”는 의미를 가지는 Boundary 정보로 동작하며, full/empty 판단에는 이 경계 정보만으로 충분하다.

 

 

Reference:

https://secondspot.tistory.com/24#google_vignette

[4] Clifford E. Cummings, “Simulation and Synthesis Techniques for Asynchronous FIFO Design,” SNUG 2002 http://www.sunburst-design.com/papers/CummingsSNUG2002SJ_FIFO1.pdf