런렝스 제한
Run-length limitedRLL 부호화는 대역폭 제한이 있는 통신 채널을 통해 임의의 데이터를 전송하기 위해 사용되는 라인 부호화 기법입니다.RLL 코드는 m, n, d, k의 4가지 주요 파라미터로 정의됩니다.첫 번째 2개의 m/n은 코드의 레이트를 나타내고 나머지 2개는 연속된1개의 제로 사이의 최소d와 최대k의 수를 지정합니다.이것은 고정 기록 헤드를 지나 미디어를 이동하는 통신 시스템과 스토리지 시스템 모두에서 사용됩니다.
특히 RLL은 신호가 변경되지 않는 반복 비트의 연장(런) 길이를 제한합니다.실행이 너무 길면 클럭 복구가 어렵고, 너무 짧으면 통신 채널에 의해 고주파가 감쇠될 수 있습니다.데이터를 변조함으로써 RLL은 저장된 데이터를 디코딩할 때 타이밍의 불확실성을 줄여주므로 데이터를 다시 읽을 때 비트가 잘못 삽입되거나 제거될 수 있습니다.이 메커니즘에 의해 비트 간의 경계를 항상 정확하게 찾을 수 있습니다(비트 슬립 방지).또한 미디어를 효율적으로 사용하여 주어진 공간에 최대량의 데이터를 안정적으로 저장할 수 있습니다.
초기 디스크 드라이브에서는 RLL(0,1) FM 코드와 같은 매우 단순한 인코딩 방식을 사용했으며, 그 뒤를 이어 RLL(1,3) MFM 코드가 1980년대 중반까지 하드 디스크 드라이브에 널리 사용되었으며 CD, DVD, MD, Hi-MD, Blu-ray 등의 디지털 광학 디스크에서 여전히 사용되고 있습니다.고밀도 RLL 코드(2,7)와 RLL 코드(1,7)는 1990년대 초까지 하드 디스크의 사실상의 업계 표준이 되었습니다.
RLL 코딩의 필요성
하드디스크 드라이브에서는 정보가 디스크상의 자기장 방향의 변화로 표현되며, 자기매체상에서는 재생출력이 플럭스 천이의 밀도에 비례한다.컴퓨터에서는 정보가 와이어상의 전압으로 나타난다.정의된 접지 레벨과 관련된 와이어의 전압은 바이너리 0이 아니며 접지와 관련된 와이어의 양의 전압은 바이너리 0을 나타냅니다.반면, 자기 매체는 항상 자속을 운반합니다 – "북극" 또는 "남극".자기장을 바이너리 데이터로 변환하려면 몇 가지 부호화 방법을 사용하여 둘 사이를 변환해야 합니다.
가장 간단한 실용적인 코드 중 하나인 수정 NRZI는 단순히 1을 자기 극성 전이(flux reversion이라고도 함)로 인코딩하고 0을 무전이(no transition)로 인코딩은 1을 자기 극성 전이(flux reversion)라고도 합니다.디스크가 일정한 속도로 회전하는 경우, 각 비트는 해당 비트를 나타내는 자기 신호에 대해 동일한 시간 주기, 즉 "데이터 창"이 주어지고 플럭스 반전이 이 창의 시작 부분에서 발생합니다.(주: 오래된 하드 디스크는 디스크 전체의 데이터 창으로 고정 시간을 사용했지만 최신 디스크는 더 복잡합니다. 자세한 내용은 존 비트 기록을 참조하십시오.)
이 방법은 그다지 간단하지 않습니다.재생출력은 1의 밀도에 비례하기 때문에 제로가 길면 재생출력이 전혀 없습니다.
간단한 예에서는 데이터 창이 1ns(1나노초 또는 10억분의 1초)인 바이너리 패턴 101을 생각해 보겠습니다.이것은 변경사항으로 디스크에 저장되며, 그 후 변경되지 않고 다시 변경됩니다.앞의 자기 극성이 이미 양의 경우, 결과 패턴은 --+와 같습니다. 255의 값 또는 모든 2진수 값은 -+-+- 또는 +-+-+++-로 작성됩니다.0 바이트는 ++++++++ 또는 -------로 씁니다.512바이트의 0 섹터는 동일한 극성을 가진 4096개의 순차 비트로 작성됩니다.
디스크 드라이브는 물리적 하드웨어이기 때문에 모터 속도의 변화 또는 디스크 플래터의 열팽창에 따라 드라이브의 회전 속도가 약간 달라질 수 있습니다.플로피 디스크상의 물리 미디어도 변형되어 타이밍 에러가 커질 수 있습니다.또, 컨트롤러 자체의 타이밍 회로에 따라서는, 속도의 편차가 적은 경우가 있습니다.문제는 0 문자열이 길면 디스크 드라이브의 컨트롤러가 읽기 헤드의 정확한 위치를 알 수 없기 때문에 정확히 몇 개의 0이 있는지 알 수 없다는 것입니다.실제 플로피 드라이브보다 정밀도가 높은 0.1%의 속도 변화라도 4096비트 데이터 스트림에 4비트가 추가 또는 삭제될 수 있습니다.어떠한 형태의 동기화 및 오류 수정이 없으면 데이터를 완전히 사용할 수 없게 됩니다.
또 다른 문제는 자기 매체 자체의 한계입니다. 특정 공간 내에서 많은 극성 변화를 쓰는 것만이 가능하기 때문에 몇 개의 극성 변화를 순차적으로 쓸 수 있는지에 대한 상한이 있습니다.이것은 선형 속도와 헤드 갭에 따라 달라집니다.
이 문제를 방지하기 위해 단일 이진수 값의 긴 반복이 발생하지 않도록 데이터가 코드화됩니다.연속적으로 기입되는 제로수를 제한함으로써, 드라이브 컨트롤러가 동기 상태를 유지할 수 있습니다.연속해서 기입되는 개수의 제한에 의해, 전체적인 극성 변화의 빈도가 감소해, 드라이브가 같은 공간에 더 많은 데이터를 격납할 수 있게 되어, 같은 용량의 데이터를 격납하기 위한 보다 작은 패키지 또는 같은 사이즈의 패키지에 격납할 수 있게 됩니다.
역사
자기 디스크에 기록하는 데 사용되는 모든 코드는 무전이 실행의 길이를 제한하므로 RLL 코드로 특징지을 수 있습니다.가장 초기의 가장 단순한 변형에는 수정 주파수 변조(MFM)와 같은 특정 이름이 부여되었으며, "RLL"이라는 이름은 일반적으로 그러한 특정 이름이 부여되지 않은 보다 복잡한 변형에만 사용되지만 기술적으로 모든 변형에 적용됩니다.
하드 드라이브에 사용된 최초의 "RLL" 코드는 RLL(2,7)로, IBM 엔지니어가 개발했으며 IBM 3370 DASD에서 [1][2][3]4300 시리즈 메인프레임과 함께 사용하기 위해 1979년에 상용화되었습니다.1980년대 후반 PC 하드 디스크는 RLL을 사용하기 시작했습니다(즉, MFM과 같은 고유 이름을 받은 것보다 더 복잡한 변형). RLL 코드는 1980년 이후 광디스크 기록 관행에서 거의 보편적으로 사용되고 있습니다.가전제품에서는 EFM 코드(속도 = 8/17, d = 2, k = 10)와 같은 RLL이 콤팩트 디스크(CD)와 MiniDisc(MD)에, 그리고 DVD에 사용되는 EFMPluus 코드(속도 = 8/16, d = 2, k = 10)에 사용됩니다.매개 변수 d와 k는 최소 및 최대 허용 실행 길이입니다.스토리지 기술에 대한 자세한 내용은 이 문서에서 인용한 참조 자료를 참조하십시오.[4][5]
기술 개요
일반적으로 실행 길이는 신호가 변경되지 않은 비트 수입니다.비트 1의 런길이 3은 시퀀스 111을 나타낸다.예를 들어 디스크의 자기 편광 패턴은 +---+++++++이며 길이가 1, 4, 2, 3, 및 6일 수 있습니다.단, run-length 제한 부호화 용어는 NRZI 부호화를 상정하고 있기 때문에 1비트는 변경을 나타내고0비트는 변경을 나타내지 않습니다.상기의 시퀀스는 1100010100000001로 나타나며 0비트의 실행만 카운트됩니다.
다소 혼란스러운 것은 실행길이는 인접한 것 사이의 제로(0, 3, 1, 2, 5)의 수로, 실제로 신호가 변경되지 않은 비트 횟수보다 1회 적다는 것입니다.실행 길이 제한 시퀀스는 두 개의 파라미터 d와 k로 특징지어지며, 이 파라미터는 시퀀스에서 발생할 수 있는 최소 및 최대 제로 비트 실행 길이를 규정합니다.따라서 RLL 코드는 일반적으로 (d,k) RLL(예: (1,3) RLL)로 지정됩니다.
코딩
부호화 형식에서 "1" 비트는 플럭스 천이를 나타내고 "0" 비트는 디스크의 자기장이 해당 시간 간격 동안 변경되지 않음을 나타냅니다.
FM: (0,1) RLL
일반적으로 "RLL 코드"라는 용어는 보다 정교한 인코딩을 나타내기 위해 사용되지만, 원래의 주파수 변조 코드(Differential Manchester Encoding이라고도 함)는 단순한 레이트 1/2 RLL 코드라고 볼 수 있습니다.추가된 1비트를 클럭비트라고 부릅니다
| 데이터. | 부호화 |
|---|---|
| 0 | 10 |
| 1 | 11 |
예:
데이터: 0 0 1 1 1 0 0 0 0 0 1 0 0 1 부호화: 1010111110101010111010101010 클럭: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
GCR: (0, 2) RLL
최대 실행 길이를 인접한 2개의 0비트로 확장함으로써 데이터 속도를 4/5로 개선할 수 있습니다.이것은 원래의 IBM 그룹 코드 레코딩 변형입니다.
|
|
가능한 경우(16개의 코드 중 11개), 비트 패턴abcd는, 다음과 같이 프리픽스 하는 것으로 부호화 됩니다.aabcd규칙 중 하나를 위반하는 5가지 경우(000d또는ab0011로 시작하는 코드가 대체됩니다( ).11bea여기서 e = a ∨ d).
예:
데이터: 0010 1101 0001 1000 부호화: 100100110111010
(0.2) RLL의 정의를 충족시키려면 각 5비트코드에 2개 이하의 연속0이 포함되어 있는 것만으로 충분할 뿐만 아니라 조합된5비트코드의 모든 쌍이 연속0을 2개 이하로 할 필요가 있다는 점에 주의해 주세요.즉, 임의로 선택한2개의 코드에 대해 첫 번째 코드의 마지막 1비트와 두 번째 코드의 첫 번째 1비트 사이에 0을 2개 이상 둘 수 없습니다.이는 모든 RLL 코드에 대해 실행 길이 제한(이 경우 0과 2)이 플레인 데이터 비트의 이산 시퀀스를 나타내는 RLL 코드 컴포넌트뿐만 아니라 전체 변조 비트스트림에 적용되기 때문입니다.(입력 데이터는 임의의 비트시퀀스일 수 있기 때문에 예외 없이 이 규칙은 임의의 코드쌍에 대해 유지되어야 합니다).위의 IBM GCR 코드는 이 조건을 충족합니다. 왜냐하면 모든 5비트 코드의 시작 부분에서 0의 최대 실행 길이가 1이고, 마찬가지로 모든 코드의 끝 부분에서 최대 실행 길이가 1이므로 인접 코드 사이의 결합 부분에서 총 실행 길이가 2가 됩니다.(상기의 예에서는 코드 간에 발생하는 최대 런 길이의 예를 볼 수 있습니다.여기서 데이터 "0010"의 코드는 0으로 끝나며 다음 데이터 "1101"의 코드는 0으로 시작하여 이들 2개의 5비트 코드의 접합부에 2개의 0으로 런을 형성합니다.)
MFM: (1, 3) RLL
수정된 주파수 변조는 그 특별한 특성이 임의의 비트 스트림의 두 배 밀도의 자기 매체에 비트를 쓸 수 있게 해주기 때문에 흥미로워지기 시작합니다.판독 장비가 이를 감지하기 위해 시간 플럭스 전환에 얼마나 근접할 수 있는지에 대한 제한이 있으며, 이는 미디어에 비트를 얼마나 가깝게 기록할 수 있는지를 제한합니다.최악의 경우 임의의 비트스트림에서는 2개의 연속된 플럭스 천이를 시간 내에 생성하기 때문에 비트는 판독기가 이를 검출할 수 있을 만큼 충분히 떨어져 있어야 합니다.그러나 이 코드는 d = 1의 제약을 가한다. 즉, 두 코드 사이에는 각각 최소 1개의 0이 존재한다.즉, 최악의 경우 플럭스 전환은 2비트 간격으로 이루어지기 때문에 판독기의 기능을 초과하지 않고 임의의 비트스트림보다 2배 가까이 접근할 수 있습니다.
이 2배의 기록 밀도는, 이 코드의 1/2 부호화 레이트를 보상해, 레이트 1 코드에 상당합니다.
| 데이터. | 부호화 |
|---|---|
| 0 | x0 |
| 1 | 01 |
여기서 "x"는 이전 인코딩 비트(이전 데이터 [clarification needed]비트이기도 함)의 보완입니다.클럭 비트 ("x" 비트)와 "01" 코드의 "0" 비트)를 제외하고, 이것은 FM 테이블과 같으며, 이것이 이 코드가 이름을 얻는 방법입니다.삽입된 클럭비트는 2개의 0 데이터 비트 사이를 제외하고0 입니다
예:
데이터: 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
(1,7) RLL
(1,7) RLL은 2비트의 데이터를 디스크상의 3비트에 매핑하고 인코딩은 2비트 또는4비트 그룹으로 이루어집니다.부호화 규칙은 (x, y)가 (NOT x, x AND y, NOT y)가 되는 것을 제외하고 (x, 0, 0, y)는 (NOT x, x AND y, NOT y, 0, 0)[6]이 됩니다.다음 표에 따라 인코딩할 경우 가장 긴(테이블의 마지막) 일치를 사용해야 합니다.이러한 일치는 앞의 규칙을 적용하면 코드 제약 조건이 위반되는 예외 처리 상황입니다.
| 데이터. | 부호화 |
|---|---|
| 00 | 101 |
| 01 | 100 |
| 10 | 001 |
| 11 | 010 |
| 00 00 | 101 000 |
| 00 01 | 100 000 |
| 10 00 | 001 000 |
| 10 01 | 010 000 |
예:
데이터: 0 0 1 1 0 1 0 0 0 0 1 0 1 0 부호화: 101 001 010 100 000 001
(2,7) RLL
(2,7) RLL은 레이트-MFM과 같이 디스크의 2n비트에 n비트의 데이터를 매핑하는 1⁄2 코드이지만 최소 실행 길이가 50% 더 길기 때문에 비트 쓰기 속도가 빨라져 50% 더 높은 유효 데이터 밀도를 달성할 수 있습니다.인코딩은 2비트, 3비트 또는 4비트 그룹으로 이루어집니다.
Western Digital WD5010A, WD5011A, WD50C12
| 데이터. | (2,7) RLL 부호화 |
|---|---|
| 11 | 1000 |
| 10 | 0100 |
| 000 | 100100 |
| 010 | 000100 |
| 011 | 001000 |
| 0011 | 00001000 |
| 0010 | 00100100 |
Seagate ST11R, IBM
| 데이터. | (2,7) RLL 부호화 |
|---|---|
| 11 | 1000 |
| 10 | 0100 |
| 000 | 000100 |
| 010 | 100100 |
| 011 | 001000 |
| 0011 | 00001000 |
| 0010 | 00100100 |
Perstor Systems ADRC
| 데이터. | (2,7) RLL 부호화 |
|---|---|
| 11 | 1000 |
| 10 | 0100 |
| 000 | 100100 |
| 010 | 000100 |
| 001 | 001000 |
| 0111 | 00001000 |
| 0110 | 00100100 |
부호화된 형식은 최대 4에서 시작하여 최대 3개의 제로 비트로 끝나 최대 실행 길이가 7입니다.
예:
데이터: 1 1 0 1 0 0 1 부호화: 1000 001000 00001000
HHH(1,13)
HHH(1,13) 코드는 16MB/s IrDA VFIR 물리적 [7]계층에서 사용하기 위해 3명의 IBM 연구원(Hirt, Hassner 및 Heise)에 의해 개발된 속도 2/3 코드입니다.자기 인코딩과 달리 이 기능은 적외선 송신기용으로 설계되었습니다.여기서 0비트는 꺼짐, 1비트는 켜짐을 나타냅니다.1비트는 전송에 더 많은 전력을 소비하기 때문에 1비트의 밀도를 50% 미만으로 제한하도록 설계되어 있습니다.특히, 이것은 (1,13 5) RLL 코드입니다.마지막 5는 최대 5개의 연속적인 "10" 비트쌍이 있다는 추가 제약을 나타냅니다.
| 데이터. | 부호화 |
|---|---|
| 00 | 010 |
| 01 | 001 |
| 10 | 100 |
| 11 | 101 |
| 01 10 | 001 000 |
| 01 11 | 010 000 |
| 11 10 | 101 000 |
| 11 11 | 100 000 |
| 00 11 00 | 010 000 000 |
| 00 11 01 | 001 000 000 |
| 10 11 00 | 100 000 000 |
| 10 11 01 | 101 000 000 |
| 00 11 10 11 | 010 000 000 000 |
| 10 11 10 11 | 100 000 000 000 |
첫 번째 8행은 표준(1,7) RLL 코드를 나타냅니다.추가 6개의 예외는 0의 최대 런을 13으로 증가시키지만(법률 패턴 100 000 000 000 001에서 10 11에 이어 01) 최대 평균 1 밀도를 1⁄3으로 제한한다.1~0 쌍의 최장 실행은 000 101 010 101 000입니다.
이 코드는 1의 밀도를 1⁄12 ~1⁄3으로 제한하고 평균 25.8%로 합니다.
예
예를 들어 비트시퀀스 10110010을 다른 인코딩으로 인코딩합니다.
| 부호화 | 데이터. | 부호화 |
|---|---|---|
| RLL(0,1) | 10110010 | 1110111110101110 |
| RLL(0,2) | 1011 0010 | 01011 10010 |
| RLL(1,3) | 10110010 | 0100010100100100 |
| RLL(1,7) | 10 11 00 10 | 001 010 101 001 |
| RLL(2,7) | 10 11 0010 | 0100 1000 00100100 |
밀도
자기 테이프가 인치당 최대 3200개의 플럭스 리버스를 포함할 수 있다고 가정합니다.수정된 주파수 변조 또는 (1,3) RLL 인코딩은 각 데이터 비트를 2비트로 테이프에 저장하지만, 1비트(플럭스 반전) 사이에 1비트의 0(플럭스 반전) 비트가 있음을 보증하므로 테이프에 6400비트 또는 3200비트/인치를 저장할 수 있습니다.(1,7) RLL 부호화에서는 테이프에 6400비트/인치도 저장할 수 있지만, 2개의 데이터 비트를 저장하는 데 필요한 부호화 비트는 3비트밖에 없기 때문에 이것은 4267비트/인치입니다.(2,7) RLL 부호화에서는 각 데이터 비트를 저장하기 위해 2개의 부호화 비트가 필요하지만 임의의 1비트 사이에 2개의 0비트가 있음을 보증하기 때문에 테이프에 9600개의 부호화 비트 또는 4800개의 데이터 비트를 저장할 수 있습니다.
하드 드라이브의 플럭스 역방향 밀도는 훨씬 더 높지만, 다른 인코딩 시스템을 사용하면 스토리지 밀도의 동일한 향상을 볼 수 있습니다.
「 」를 참조해 주세요.
- 8b/10b 부호화
- 비트 슬립
- CD 및 DVD에 사용되는 DC 프리(2,10) RLL 코드입니다.
- 코드 수정 오류
- 라인코드
- 변조
- 물리층
- PRML
- 런렝스 부호화
- 자기동기코드및비트동기
- 소스 코딩
레퍼런스
- ^ IBM 연구 개발 저널, 디스크 파일 혁신의 4분의 1세기.
- ^ P. A. Franaszek(1972), "오류 전파 제한을 수반하는 런타임 제한 가변 길이 부호화", 미국 특허 3,689,899.
- ^ 50년간의 디스크 드라이브 업계 최초, DISK/TREND, Inc., 전 세계 디스크 드라이브 및 데이터 스토리지 업계의 시장 조사 출판사.web.archive.org
- ^ Kees Schouhamer Immink (December 1990). "Runlength-Limited Sequences". Proceedings of the IEEE. 78 (11): 1745–1759. doi:10.1109/5.63306.
A detailed description is furnished of the limiting properties of runlength limited sequences.
- ^ Kees A. Schouhamer Immink (November 2004). Codes for Mass Data Storage Systems (Second fully revised ed.). Eindhoven, The Netherlands: Shannon Foundation Publishers. ISBN 90-74249-27-2. Retrieved 2015-08-23.
- ^ Mee, C. Denis; Daniel, Eric D. (1996). Magnetic Storage Handbook (2nd ed.). McGraw Hill. ISBN 0-07-041275-8.
- ^ 를 클릭합니다Hirt, Walter; Hassner, Martin; Heise, Nyles (February 2001), "IrDA-VFIr (16 Mb/s): modulation code and system design", IEEE Personal Communications, 8 (1): 58–71, doi:10.1109/98.904900.
