KR20070029756A - 인코딩 및 디코딩 장치 및 그 방법 - Google Patents

Abstract

본 발명은, 사용자 데이터 스트림(m)을 채널 데이터 스트림(y)으로 인코딩하는 인코딩 장치와 방법과, 그에 대응한 디코딩 장치 및 방법에 관한 것이다. 최악의 경우의 저장 시스템의 BER 작용을 향상시키고 신뢰도를 증가시키기 위해서, 특히 2차원 광학 저장 시스템 또는 통신 시스템에서, 특히 정보 속도의 큰 손실 없이 확실하게 BER을 낮게 한다. 본 발명에 따른 인코딩장치는, 사용자 데이터 스트림(m)을 상기 사용자 데이터 스트림(m)보다 적어도 하나 더 많은 심볼을 포함하는 중간 데이터 스트림(i)으로 변환하는 확장부와, 스크램블링 코드(C)로부터 스크램블링 스트림(c)마다 상기 중간 데이터 스트림(i)을 사용하여 그 스크램블링 스트림(c)에 대한 성능 지수의 값(v)을 반복적으로 결정하는 처리부(100,200,500,600)와, 상기 성능 지수 값(v)으로부터 최적 메리트 값(v_opt)을 선택하고 상기 성능 지수가 상기 최적의 메리트 값(v_opt)과 같은 최적의 스크램블링 스트림(c_opt)을 선택하는 선택부(300)와, 채널에 출력하기 위해 상기 채널 데이터 스트림(y)을 얻도록 상기 최적의 스크램블링 스트림(c_opt)의 심볼을 상기 중간 데이터 스트림(i)의 대응한 심볼 상에 맵핑하는 적어도 하나의 맵핑부(400)를 구비한다.

인코딩 장치, 디코딩 장치, 스크램블링 코드, 데이터 스트림.

Description

인코딩 및 디코딩 장치 및 그 방법{ENCODING AND DECODING APPARATUS AND CORRESPONDING METHODS}

본 발명은 사용자 데이터 스트림을 채널 데이터 스트림으로 인코딩하는 방법 및 인코딩 장치에 관한 것이다. 또한, 본 발명은 그에 대응한 디코딩 장치 및 방법과, 기록매체와, 본 발명에 따라 인코딩된 데이터를 갖는 신호와, 상기 방법을 실행하기 위한 컴퓨터 프로그램에 관한 것이다.

유럽특허출원 EP 02076665.5(PHNL 020368)에는, 2차원 광학 스토리지용 시스템, 특히 2차원 채널 데이터 스트림을 인코딩 및 디코딩하는 방법이 기재되어 있다. 2차원 광학 스토리지의 목적은, 저장밀도, 예를 들면 동일한 물리적 판독 시스템(파장, 개구수)을 사용한 블루레이 디스크(BD)보다 2.0배 높게 하는데 있다. 상기 제시된 2차원 광학 스토리지 시스템의 일 구성요소는, 광학매체의 비트(멀티레벨 심볼) 셀로 2차원 6각형 격자를 사용하는 것이다. 그래서, 각 비트(심볼)는, 6개의 최근접 이웃비트를 갖는다. 상기 최근접 인접 비트만을 포함하는 제 1 쉘(shell) 근사법에서, 2차원 지수 i를 갖는 특정 입력 비트 x_i보다 위에 판독 스폿이 있는 경우 채널 출력은, 입력비트와, 1과 동일한 6개의 최근접 인접 비트의 수의 함수이다. 이러한 수를 z_i라고 부른다.

도 1은 10x_i+z_i의 함수로서 채널 출력의 제 1 쉘 근사법을 도시한 것이다. 그래서, 6개의 0 비트들로 둘러싸인 0 비트인 경우는 본 도면의 곡선의 최좌측점에 해당한다. 6개의 1 비트들로 둘러싸인 1 비트인 경우는 곡선의 최우측점에 해당한다. 도 2에는, 서로 다른 클러스터 형태의 7-비트 6각형 클러스터가 도시되어 있다.

비트오류율(BER)은, 채널 입력 x의 시퀀스(2차원 격자)에 의존하고, 이 시퀀스는 채널 입력 필드라고 부르고, 채널 입력 필드가 모두 1로 이루어진 경우 가장 나쁘다. 그후, (평균) 비트오류율(BER)은, 전형적인 랜덤 입력 메시지에 대해서보다 더욱 나쁘다. 가산성 백색 가우스 잡음(AWGN) 채널 모델이 사용되는 경우, 최악의 경우의 모든 입력 필드에 대한 BER은 2개의 서로 다른(무잡음) 채널 출력 필드간의 최소 제곱 유클리드 거리에 의해 결정된다.

동일한 판독 물리학을 사용하면서 1차원 광학 스토리지의 저장밀도를 초과하는 저장밀도를 위한 2차원 광학 스토리지에 대해, 서로 다른 채널 출력 필드간의 최소 제곱 유클리드 거리는, 6개의 최근접 인접 비트가 모두 1인 한 쌍의 채널 입력 필드에 대해 일어나고, 중앙 비트는 0 또는 1이고, 그 외의 모든 비트는 모두 1이다. 이러한 사실은 아는데 돕도록, 도 1의 곡선에서 z(z=0,1,...,6)번째 점과 10+z번째 점 사이의 수직거리(의 제곱)가 z=6일 경우 최소라는 사실을 설명할 수 있다. 보다 정확하게는, 이러한 (제곱) 차이는, (0 또는 1 중 한쪽임 - 차이에 의해 일어남) 상기 중심 비트 위치(지수) 보다 위의 채널 출력에서의 (제곱) 차이뿐 만 아니라 상기 중심 비트의 최근접 인접 비트 보다 위의 채널 출력에서의 6(제곱) 차이도 총 제곱 유클리드 거리에 기여하기 때문에 전체 이야기를 말하지 않는다. 예를 들면, z=6일 경우, 후자의 6보다 작은 기여는 각각 도 1의 곡선에서 2번째와 3번째 점 사이의 (제곱) 거리에 대응한다.

대향 중심비트를 갖는 (채널 입력의) 클러스터에 대응하는 채널 출력 필드들간의 총 제곱(유클리드) 거리는, 가산성 백색 가우스 잡음(AWGN)을 갖는 채널을 사용하여 상기 중심비트를 구별할 수 있는 신뢰성 있는 측정값이다.(상술한 클러스터는 상기 중심비트보다 더 많은 지수에 있어서 다를 수도 있다.). 서로 다른 잡음 성질을 갖는 채널에 대해서, 서로 다른 거리 또는 구별 측정값을 정의할 수 있다.

2차원 광학 스토리지가 특정 채널 입력 필드에 대해 신뢰 가능하지 않을 수도 있는 경우를 방지하기 위해서, 제약 코딩을 사용하여 도 1의 곡선의 최우측점(즉, 도 2의 최우측 클러스터 타입)을 금지한 것을 생각하였다. 제약 코딩은, (d;k) 제약 코딩이 특별한 경우인 학습법의 아주 일반적인 용어이다. 예를 들면, 하나의 비트가 6개의 1비트로 둘러싸인 경우를 제외할 수 있다. 이와 같은 제약에 대한 정보 속도(information rate) 손실은 허용 가능하다. 그러나, 또 한편으로는, 하나는 6개 중에서 5개의 최근접 인접 비트가 1이고 중심비트가 0 또는 1인 경우의 최소 거리와 대비된다. 이러한 경우의 그 제곱 유클리드 거리는 우리가 이전에 가졌던 최소 유클리드 거리보다 근소하게만 크다. 이것이 의미하는 것은, 우리도 도 1의 곡선에서 최우측점(z=5,x=1) 이외의 점(즉, 도 2에서 최우측 클러스터 타입 이외의 타입)을 금지해야 한다는 것이다. 랜덤 입력 메시지에 대해서, 1인 최근접 인 접의 z의 발생 분수는 이항식 계수

에 비례한다. 결과적으로, z=5, x=1을 제외하는 것은, z=6,x=1을 제외하는 것보다

배 더 값비싸다. 이러한 방식의 (국부적) 제약 코딩은 상당히 상기 정보 속도를 감소시키지만 기본 방식에 있어서 평균 신뢰도를 갖는 데이터 의존도를 해결하지 못한다. 국부적 제약으로부터 벗어나려는 다른 시도에 대해서, 주목해야 하는 것은, 약하게 제약된 코드가 존재한다는 것이고, 여기서 특정의 금지된(forbidden) 국부적 패턴은 가능성이 약간 낮게 일어나도록 허용된다.

도 1의 금지 점(즉, 도 2에 도시된 서로 다른 클러스터 타입의 단일 클러스터 타입) 이전에, 실현해야 하는 것은, 이 곡선 상의 모든 점이 전형적인 랜덤 입력 메시지에 대해 일어난다는 것이다. 상기와 같은 전형적인 랜덤 메시지에 대해, 1과 동일한 6개의 최근접 인접 비트를 갖는 비트의 분수는 작다(1/64). 더욱 오류가 나기 쉬운 경우의 상기 분수의 작음은 BER에 대해 그들의 기여도를 경감한다. 이러한 분수가 더 이상 작지 않은 경우(예를 들면, 전형적인 분수의 2배보다 큰, 즉 1/32) 문제가 생긴다. 이러한 의견은, z의 소정 값을 갖는 클러스터의 발생 분수에 제약을 두도록 제안한다. 이들 분수는, 임의의 허용된 입력 메시지 필드에 대해 정확히 랜덤한 경우로부터 실질적으로 벗어나지 않아야 한다. 이것은, 랜덤한 입력 메시지에서 평균화된 BER과 본질적으로 동일하도록 허용된 모든 입력 메시지에서 BER의 최악의 경우에 대해 충분한 상태이다. 상술한 분수를 측정하기 위해 논 리적 스트림 크기는, 예를 들면, 오류 제어 코드(오류 정정코드, 오류 검출코드)의 스트림 크기이고, 그 코드의 디코더는 비트 검출기가 후속한다.

본 발명의 목적은, 상술한 문제점을 해결하는 인코딩 장치 및 방법을 제공하고, 최악의 경우의 저장 시스템의 BER 작용을 향상시키고 신뢰도를 증가시키고, 특히 2차원 광학 저장 시스템 또는 통신 시스템에서, 특히 정보 속도의 큰 손실없이 확실하게 BER을 낮게 한다. 또한, 대응한 디코딩 장치와 방법과, 상기 인코딩 및/또는 디코딩 방법을 컴퓨터 상에서 실행하기 위한 컴퓨터 프로그램을 제공한다.

본 발명에 따른 상기 목적은, 청구항 1에 기재된 것과 같은 인코딩 장치에 의해 달성되고, 이 인코딩 장치는,

- 상기 사용자 데이터 스트림을 상기 사용자 데이터 스트림보다 적어도 하나 더 많은 심볼을 포함하는 중간 데이터 스트림(i)으로 변환하는 확장부와,

- 스크램블링 코드로부터 스크램블링 스트림마다 상기 중간 데이터 스트림을 사용하여 그 스크램블링 스트림에 대한 성능 지수의 값을 반복적으로 결정하는 처리부를 구비하고, 상기 스크램블링 스트림이 상기 중간 데이터 스트림처럼 동등하게 많은 수의 심볼을 포함하고, 상기 성능 지수는 상기 스크램블링 스트림의 부분의 집합에 걸친 합이고, 상기 부분은 상기 스크램블링 스트림으로부터 적어도 2개의 심볼 위치를 포함하고, 상기 합의 각 항은 상기 중간 스트림의 대응한 부분을 사용하여 스크램블링 스트림의 상기 부분에 대한 성능 지수이고, 상기 스크램블링 스트림의 상기 부분 각각에서 각기 가능한 심볼의 조합은 상기 스크램블링 코드로부터 동등하게 많은 스크램블링 스트림에서 일어나고,

- 상기 성능 지수 값으로부터 최적 메리트값을 선택하고 상기 성능 지수가 상기 최적의 메리트 값과 같은 최적의 스크램블링 스트림을 선택하는 선택부를 더 구비하고,

- 채널에 출력하기 위해 상기 채널 데이터 스트림을 얻도록 상기 최적의 스크램블링 스트림의 심볼을 상기 중간 데이터 스트림의 대응한 심볼 상에 맵핑하는 적어도 하나의 맵핑부를 더 구비한다.

본 발명은 인코딩 처리에서 국부적 랜덤화기를 도입한다는 아이디어에 기초한다. 유도 스크램블링(guided scrambling)은, 저장 시스템에의 입력을 랜덤화하고 (성능 지수라고도 불리는) 특정 오브젝트 함수를 최대화하는 잘 알려진 기술이다. 원격통신 시스템에서는, 스크램블링 또는 랜덤화를 포함하는, 예를 들면 변조된 신호의 비정상 스펙트럼 특성("아주 뾰족한 상태(too peaky)")을 막거나 또는 간섭의("뾰족한" 스펙트럼을 갖는) 영향을 분산시키는 것이 잘 알려진 관행이다. 광 기록 분야에서, 상기와 같이 유도 스크램블링은, K.A.Schouhamer Immink, "Codes for Mass Data Storage Systems," Shannon Foundation,Rotterdam,1999,chapter 13에 기재되어 있다.

본 발명에 따른 평균 예상 비트오류율은, 하나의 상기 오브젝트 함수(성능 지수)로서 표현될 수 있고, 이러한 오브젝트 함수의 선형성(평균)은 이용된다. 증명된 것은, 임의의 입력 시퀀스에 대해, 작은 스크램블링 코드에는 스크램블링 코드어가 존재하고, 이를 위해 상기 예상 비트오류율은 랜덤 입력 데이터에 대해서도 다름없다는 것이다. 마찬가지로, 본 발명은, 최악의 경우의 (필터링) 통신 시스템 의 평균 전력이 그것의 랜덤한 평균 이하(이상)로 하도록 적용될 수 있다.

2차원 광학 스토리지에서처럼 2차원 6각형 격자에 비트를 저장하는 경우, 본 발명의 스크램블링 방법은, 본 발명을 적용한 스트림 당 6개의 정보 비트를 필요로 한다. 따라서, 스트림이 길면, 속도 손실이 작지만, 국부적으로 BER은 그래도 클 수 있다. 입력 시퀀스마다(2차원 격자), 64개의 스크램블링 코드어에 대해서만 예상된 평균 비트 오류율 함수의 값을 구할 필요가 있다. 본 발명의 방법은, 이의 값을 효율적으로 구할 수 있다.

본 발명에 따른 디코딩 장치는, 청구항 13에 기재되어 있고,

- 상기 채널 데이터 스트림을 상기 오류정정코드의 채널 코드어로 디코딩하는 ECC 디코딩부와,

- 스크램블링 코드어를 중간 데이터 스트림에 맵핑하는 것이 상기 채널 코드어에서 생기도록 상기 채널 코드어로부터 중간 데이터 스트림과 스크램블링 코드어를 찾는 분리부와,

- 사용자 데이터 스트림을 사용자 데이터 스트림보다 적어도 하나 더 많은 심볼을 포함하는 중간 데이터 스트림으로 확장하는 것이 상기 중간 데이터 스트림에서 생기도록 상기 중간 데이터 스트림으로부터 사용자 데이터 스트림을 검색하는 역맵핑부를 구비한다.

또한, 본 발명은, 청구항 1에 기재된 인코딩 방법에 따라 사용자 데이터 스트림(m)을 인코딩하는 채널 데이터 스트림(r)을 저장하는 청구항 15에 기재된 것과 같은 기록매체에 관한 것이다.

상기에 대응한 인코딩 및 디코딩 방법은, 청구항 12 및 14에 기재되어 있다. 본 발명의 바람직한 실시예는, 종속항에 기재되어 있다. 본 발명의 인코딩 방법에 따라 인코딩된 신호는, 청구항 16에 기재되어 있다. 상기 방법들을 실행하기 위한 컴퓨터 프로그램은, 청구항 17에 기재되어 있다.

바람직한 실시예에서는 히스토그램을 사용한다. 히스토그램 방법의 이점은, 중간 스트림을 가능한 모든 스크램블링 코드어에 맵핑하고 이들의 가능한 모든 선택에 대한 성능 지수의 값을 구할 필요가 없다는 것이다. 스크램블링 코드 C에 총 다수의 ｜C｜스크램블링 코드어가 있고 그 코드어가 K와 동일한 (블록) 길이를 갖는 경우, 모든 가능성에 대한 성능 지수의 평가의 총 복잡도는 곱이다(｜C｜K). 히스토그램 방법의 이점은, 계산상 복잡도가 블록 길이 K가 큰 경우 더욱 감소된다는 것이다. 그 히스토그램 방법은, 한번 중간 시퀀스를 주사하여 히스토그램을 생성한다. 이것의 복잡도는 K이다, 즉 1회의 블록길이이다. 상기 히스토그램을 조작하는데의 복잡도는 카운트만을 다루므로, 블록길이 K와 상관없다는 것을 주목한다. 이들 카운트의 수치 범위는, K의 대수에만 비례할 뿐이다. 블록길이 K가 매우 큰 경우, 후자의 복잡도는 히스토그램을 컴파일하기 위해 중간 시퀀스 i를 주사하는 상술한 복잡도에 대해 무시될 수 있다.

일반적으로, 수신기는, 메시지("역스크램블")를 검색하도록 주어진 메시지 m을 위해 사용되었던 스크램블링 코드어 c의 선택이 통지될 필요가 있다. 본 발명에 의하면, 이러한 선택은, 확장부에 의해 전송되고, 이 확장부는, 그 메시지를 중간 스트림으로 연장하여서, 중복성의 형태를 추가한다. 이러한 중복성은, 청구항 10에 기재된 것과 같은 메시지 스트림과 공지된 심볼을 연관시키는 형태를 취하거나, 청구항 11에 기재된 것과 같은 오류정정 인코딩 변환의 형태를 취할 수 있다.

오류정정 코드는, 본질적으로 중복 코드이다. 이들 또는 다른 형태의 중복성을 중간 스트림의 구성에 있어서 메시지 스트림에 추가하는 것에 의해, 인코딩 동작시에 스크램블링 코드어를 사용하는 선택(불확실성)이 수신기에 의해 검출될 수 있다. 예를 들면, 청구항 10일 경우에, 삽입된 공지된 심볼이 존재하는 코드어 내에 위치(지수)에 있어서, 상술한 위치에 있는 심볼의 값으로부터 공지된 심볼을 역맵핑(예를 들면, 청구항 3에 기재된 것과 같이 감산)하는 것에 의해 스크램블링 코드어의 심볼(예를 들면, 바이트)을 검색할 수 있다.

실제의 많은 경우에, 채널 데이터 스트림은, 잡음, 소거 및 다른 채널 오류로 교란될 수 있다. 청구항 10에 기재된 것과 같은 실시예를 사용하는 경우에, 공지된 심볼의 위치에 있는 상기 수신된 채널 데이터 스트림(보내진 채널 데이터 스트림의 잡음성 복사)은, 채널 잡음의 유무에 의해 오류 상태로 수신되면, 이것에 의해 수신기는 스크램블링 코드어를 잘못 선택했다고 판단할 것이다. 따라서, 수신기는, 상기 수신된 채널 데이터 스트림과 상기 잘못 선택한 스크램블링 코드어를 역맵핑하고(예를 들면, 맵핑 동작이 청구항 3에 기재된 것과 같은 가산 연산일 경우 감산하고), 전체 디코딩 오류가 생겨, 일반적으로 그 디코딩된 메시지에서 다수의 심볼오류가 생길 수 있다. 따라서, 이러한 경우에 오류 전달 현상이 관측된다. 이러한 심볼 오류의 급증을 막기 위해서, 그 스크램블링 코드어의 선택을 오류제어 코딩(오류 정정 코딩)에 의해 보호되도록 상기 수신기에 전달될 필요가 있다. 일반 적으로, 채널 오류의 유무에 있어서, 나머지 중간 심볼 스트림 I를 오류 정정 코딩으로 보호하는데도 필요하다. 서로 다른 오류 정정(제어)방식을 사용하여 신뢰성 있게 스크램블링 코드어의 선택을 수신기에 전달하고, 신뢰성 있게 실제의 페이로드, 즉 공지된 심볼(들)을 제외한 나머지 중간 심볼 스트림을 전달하는 경우, 2개의 오차 정정 인코더와 디코더가 필요하다. 특히, 스크램블링 코드어의 선택이 소량의 정보(예를 들면, 1바이트 또는 1개의 10-비트 심볼, 또는 훨씬 보다 소수의 비트)이므로, 별도의 오류 정정 인코딩을 상기 소량의 정보에 적용하는 경우, 이것은 매우 작은 블록길이를 갖는 오류 정정코드를 필요로 할 것이다.

청구항 11에 기재된 것과 같은 실시예의 첫 번째 이점은, (각기 수신기에서 별도의 디코더를 필요로 하는) 2개의 인코더 대신에 단일 오류 제어용 인코더만을 사용하여 페이로드(메시지)와 스크램블링 코드로부터 스크램블링 코드어의 선택을 보호한다는 것이다. 더욱이, 이러한 실시예의 사용에 의해, 매우 작은 블록길이를 갖는 오류 정정 코드의 도입도 하지 않는다. 작은 블록길이를 갖는 오류 정정코드는, 본질적으로, 예를 들면 이러한 작은 코드에서 모든 비트(심볼)를 채널 오류로 인해 오류가 수신될 약간의 가능성이 있으므로, 채널 오류에 대해 약하게 보호한다. 이러한 현상은, 상기 코드의 비트들을 보다 큰 (채널) 스트림에서 약간의 거리간격을 두고 삽입하거나 또는, 청구항 11에 기재된 것과 같은 실시예를 적용하는 경우에 필요한 아주 많은 양의 중복비트 또는 심볼을 추가함으로써, 그 코드의 비트들을 확장(인터리브)하는 것에 의해 제한된 연장까지 경감될 뿐이다.

또한, 적분 오차 정정 코드 C'를 사용하는 것에 의해, 수신기가 a) C'로부터 상기 수신된 코드어가 스크램블링 코드의 가능한 ｜C'｜/｜C｜ 잉여류(coset) 중에서 어느 쪽에 존재하는지의 선택을 통해 전달된 중간 스트림과, b) 주어진 잉여류에 있는 가능한 ｜C｜ 코드어 중에서 어느 쪽에 있는 디코딩된 C'-코드어와 일치하는지의 선택을 통해 인코딩시에 사용되었던 스크램블링 코드어를 검색할 수 있다. 따라서, 수신된 정보의 총 양은, 양쪽이 신뢰성 있게 검출될 수 있는 2 부분을 제외하고 포함된다.

이하, 본 발명을 아래의 도면을 참조하여 더욱 상세히 설명하겠다:

도 1은, 서로 다른 광학 채널 판독(HF) 신호 레벨을 나타내는 6각형 격자에 2차원 코드에 대한 개략적인 신호 패턴을 도시한 것이고,

도 2는 서로 다른 클러스터 타입을 나타내는 6각형 격자에 2차원 코드에 대한 개략적인 신호 패턴을 도시한 것이고,

도 3은 코딩 시스템의 일반적인 레이아웃의 블록도,

도 4는 스트립 기반 2차원 코딩방식을 나타낸 개략도,

도 5는 본 발명에 따른 인코딩 장치의 일반적인 레이아웃의 블록도,

도 6은 도 5에 도시된 인코딩 장치의 상세도,

도 7은 본 발명에 따른 스크램블링 코드어를 발생하는 선형 피드백 시프트 레지스터를 도시하고,

도 8은 히스토그램을 사용한 본 발명에 따른 인코딩장치의 실시예의 블록도,

도 9는 도 8에 도시된 인코딩장치의 상세도,

도 10은 채널 심볼에 라벨을 할당하는 것을 나타낸 2차원 채널 데이터 스트림의 일부를 도시하고,

도 11은 스크램블링 코드어를 2차원 채널 데이터 스트림에 맵핑하는 것을 나타내고,

도 12는 스크램블링 코드어를 1차원 채널 데이터 스트림에 맵핑하는 것을 나타내고,

도 13은 인코딩 방법의 다른 실시예의 간단한 흐름도,

도 14는 디코딩 방법의 다른 실시예의 간단한 흐름도,

도 15는 디코딩 방법의 또 다른 실시예의 간단한 흐름도,

도 16은 바람직한 실시예에서 소위 람다(lambda) 트릭의 사용을 설명하는 도면이다.

도 1 및 도 2는 상술한 서로 다른 HF 신호레벨(도 1) 및 서로 다른 클러스터 타입(도 2)을 나타내는 6각형 격자에 2차원 코드에 대한 개략적인 신호 패턴을 도시한 것이다. 그들 도면은, 아래에 보다 상세히 설명된 유도 스크램블링 방법의 적용에 의해 해소될 본 발명의 기초가 되는 문제점을 나타낸다.

도 3은 데이터 저장 시스템의 전형적인 코딩 및 신호처리소자를 도시한 것이다. 입력 DI부터 출력 DO까지의 사용자 데이터의 사이클은, 인터리빙(10), 오류 제어코드(ECC) 및 변조 인코딩(20,30), 신호처리(40), 기록매체(50)에 데이터 저장, 신호 후처리(60), 이진 검출(70) 및 상기 변조 코드와 인터리브된 ECC의 디코 딩(80,90)을 포함할 수 있다. ECC 인코더(20)는, 중복성을, 다양한 잡음원으로부터 오류에 대해 보호하기 위해서 데이터에 추가한다. 그 후, 상기 ECC 인코딩된 데이터는, 채널에 대해 데이터를 변경하는, 즉 데이터를 채널 오류에 의해 보다 덜 변조되고 보다 쉽게 채널 출력에서 검출될 형태로 조작하는 변조 인코더(30)에 전달된다. 그리고, 변조된 데이터는, 기록장치, 예를 들면 공간 광 변조기 등에 입력되고, 기록매체(50)에 저장된다. 검색 측에서, 판독장치(예를 들면, 광 검출기 장치 또는 전하결합소자(CCD))는, 디지털 데이터(이진 변조방식을 위한 화소 당 1비트)로 다시 변환되어야 하는 의사 아날로그 데이터 값으로 되돌아간다. 본 처리에서의 제 1 단계는, 의사 아날로그 도메인에서도 기록처리에서 생성된 왜곡을 원상으로 되돌리려고 하는 등화라고 불리는, 후처리단계(60)이다. 그리고, 의사 아날로그 값의 어레이는, 비트 검출기(70)를 거쳐 이진 디지털 데이터의 어레이로 변환된다. 그 후, 그 디지털 데이터의 어레이는, 먼저 변조 디코더(80)에 전달되고, 이 변조 디코더에서는 변조 인코딩에 대해 역연산을 수행한 후 ECC 디코더(90)에 전달된다.

예시에 의해, 특정한 2차원 6각형 코드는, 아래에 설명될 것이다. 그러나, 본 발명의 일반적인 아이디어와 모든 조치는, 일반적으로 임의의 2차원, 바람직하게는 선형 코드에, 보다 구체적으로는 임의의 2차원 6각형 또는 사각형 격자 코드에 적용될 수 있다. 끝으로, 일반적인 아이디어도 코드의 1차원 전개(evolution)를 특징으로 하는 판독 채널의 회전 대칭 유무로 1차원 또는 다차원 코드에 적용될 수 있다.

상술한 것처럼, 아래에서는 2차원 6각형 코드를 생각해보자. 2차원 6각형 격 자의 비트들은, 비트 클러스터라는 점에서 식별될 수 있다. 6각형 클러스터는, 인접한 격자 사이트에서 6개의 최근접 인접 사이트로 둘러싸인 중심 격자 사이트에서의 비트로 이루어진다. 이 코드는, 1차원 방향을 따라 전개한다. 2차원 스트립은, 제 1 방향에 직교하는 제 2 방향으로 서로의 위에 적층된 다수의 1차원 행으로 이루어지고, 2차원 코드가 전개될 수 있는 엔터티를 형성한다. 도 4에는 스트립 기반 2차원 코딩의 원리가 도시되어 있다. 다른 것 위에 하나가 가간섭성으로 적층된 일부의 스트립은 광 디스크에 나선형상으로 되는 폭이 넓은 2차원 밴드(이러한 밴드를 "폭넓은 나선"이라고 부름)를 형성한다. 폭넓은 나선의 연속적인 선회들 사이 또는, 인접하는 2차원 밴드 사이에, 이를테면, 1(빈) 비트 행(제로비트로 채워짐, 랜드 마크)이 위치되어도 된다.

6각형 격자에 2차원 기록을 하기 위한 신호 레벨은, 가능한 모든 6각형 클러스터의 완벽한 세트를 위한 HF 신호의 진폭값의 플롯(plot)에 의해 식별된다. 또한, 등방성 가정, 즉 채널 임펄스 응답은 원형으로 대칭이라고 가정하는 것을 이용한다. 설명의 간략함을 위해 후자의 가정을 하는 것은, 적용가능한 본 발명에 필수적인 것은 아니다. 이것이 의미하는 것은, 그것이, 7-비트 클러스터를 특징으로 하기 위해서, 중심 비트와, 최근접 인접 비트(6개의 이웃 중에서 0,1,...,6이 "1"-비트일 수 있다) 중에서 "1"-비트(또는 "0"-비트)의 수를 식별하는데 중요하다는 것이다. "0"-비트는 우리의 표현식으로 랜드-비트이다. 전형적인 "신호 패턴"은 도 1에 도시되어 있다. 연속적인 폭넓은 나선 사이에 1(빈) 비트 행의 가드 밴드를 갖는 11개의 평행한 비트 행으로 이루어진 폭넓은 나선이라고 가정하면, 도 1의 경우 는, (예를 들면, 파장이 405nm인 블루레이저 다이오드와, 개구수 NA=0.85인 렌즈를 사용하여) 블루 레이 디스크(BD) 포맷에서 사용된 것처럼) 종래의 1차원 광 기록과 비교하여 1.7배로 증가하는 밀도에 해당한다.

상술한 특허출원 EP 02076665.5(PHNL 020368)에서는 일반적으로 2차원 광학 스토리지를 설명하였지만, 여기에 설명된 변조코드인 물고기뼈 코드의 특정 실시예는 본 발명에 따라 적용되지 않는다. 본 발명은, 바람직하게는 지수 I의 세트에 관해 모든 2진 벡터의 세트의 선형(모듈로 2) 서브공간인 코드를 언급하고, 이 코드는 스크램블링 코드라고 부른다.

본 발명에서는, 유도 스크램블링 방법을 사용한다. "거의 항상" 또는 "실제로 항상" 전형적인 랜덤 출력 시퀀스를 생성하는 랜덤화는 쉽다. 거의 모든 시퀀스의 특징은, 전형적인 균일하게 랜덤한 시퀀스이므로, 무엇인가를 행할 필요는 없다. 이와는 달리, 단일 랜덤 스크램블링 시퀀스, 예를 들면, 최대 길이 시프트 레지스터 시퀀스를 취할 수 있고, 입력 시퀀스는 스크램블링 시퀀스를 갖는 모듈로 q=2가 가산될 수 있다. 이러한 스크램블링 시스템은, 잘 알려져 있다. 이러한 스크램블링 시스템이 2차원 광학 저장 시스템 등의 저장 시스템에서 사용된다고 하면, 항상 스크램블러의 입력 시퀀스(의 중요한 부분)가 스크램블링 시퀀스 또는 그것의 2의 보수와 동일한 매우 작은 가능성이 있다. 그래서, 스크램블러 출력 시퀀스는, 대표적으로 랜덤한 것 이외의 모든 것인 (부분적으로) 모두가 0이거나 모두가 1일 것이다. 그리고, 상기 비정상 시퀀스를 판독하는 것의 신뢰성도, 상술한 것처럼 "모두 1"의 경우에 허용 가능한 것 아래에 있다. 따라서, 상기와 같은 비정상의 경 우의 존재는 허용 가능하지 않다. 저장 시스템은, 모든 입력 시퀀스를 위해 그것의 신뢰성 요구사항을 만족해야 한다. 이것은, "보증된" 스크램블링의 공급을 필요로 한다.

본 발명에 의하면, 스크램블링 코드 C를 사용하여 얻어질 수 있는 특정한 이점은 이용될 것이다. I는 유한 지수 세트, 예를 들면, 비트를 저장 또는 전송하는 공간 또는 시간에 있어서 점으로 이루어진 세트로 한다. 이것의 가장 간단한 예는, 정수(지수)의 시퀀스이다. 이것의 더욱 구체적인 예는, 6각형 격자에 다수의 (비트-) 행이고, 각 비트 행은 특정 길이로 한정된다.

본 출원에서, 용어 "스트림"은 I의 각각의 지수에서의 심볼 값을 나타내는데 사용되고, 이 심볼값은 공간, 시간(또는 공간 시간)에서의 점과 연관될 수 있다. 많은 응용에서는, 심볼로 이루어진 "블록"을 포함하는 상기 스트림을 생각할 수 있다. 이하에서 용어 "코드어"를 사용하는 경우, 상기 "블록"을 실제로 "워드"라고 부른다.

여기서는, 저장되거나 전송된 비트를 언급하였지만, 마찬가지로 제안된 방법을 3진 또는 그 보다 고순위 심볼에도 적용한다. +로 나타낸 가산 연산이 심볼 알파벳에 정의된다. 비트일 경우에, 이것은, 가산 모듈로 2이다. 3진 심볼일 경우에, 이것은, 유한체 또는 링 등의 가산일 수 있다. 워드는, I로 인덱싱된 모든 위치에서 그 심볼 값으로 규정된다. 메시지와 스크램블된 메시지 모두의 예는 워드이다. 다음에, y=(y₁,y₂,....y_d)를 d개의 비트로 이루어진 스트링으로 한다. J={(j(1),j(2),...,j(d)}를 지수 세트 I의 순서가 매겨진 부분집합으로 한다. y는 i=1,2,...,d에 대해, y_i=z_j(i)가 성립하는 경우 워드 z와 일치한다. 상기 부분집합 J는 (블록에서) 스트림의 "부분" 또는 스트림의 "심볼 부분"을 특정한다. 대부분의 전형적인 실제의 경우에, 이러한 부분은 일부의 물리적 "이웃"에 해당한다. I의 부분집합 J의 집합 X, 크기 d, 워드 z 및 스트링 y=(y₁,y₂,....y_d)에 대해서, f_x(y｜z)는 y가 J에서 z와 일치하는 X에서의 세트 J의 분수(fraction)로서 정의된다. 즉, f_x(y｜z)는 상기 부분의 위치에서 발견된 심볼 스트링이 주어진 스트링 y와 일치하는 부분의 분수를 측정한다.

C를 워드의 세트로 한다; C를 스크램블링 코드라고 한다. 심볼 위치(지수)의 세트 J는, 만약, 그리고 모든 심볼값의 조합은 C로부터 동일하게 많은 수의 워드에서의 J에서 일어나는 경우, 코드 C에 대해 균형 잡힌 세트이다. 증명된 것은, 워드 m 및 스트링 y마다 모든 스크램블링 코드어 c에 대해서 취해진 f_x(y｜c+m)의 평균은, 1/q^d _.이고, 여기서 q=2는 심볼 알파벳 Q의 크기와 같다는 것이다.

이 때문에, g는 Q^d에 정의된 실제 값 함수이고, G는 워드를, G(z)=∑f_x(y｜z)g(y)로서 (부동 소수점) 수로 맵핑하는 함수이고, 이때 합은 모든 q^d길이-d 스트링 y에 걸쳐서 확대된다. 그후, 워드 m마다, 스크램블링 코드 C로부터 모든 워드에 대한 G(m+c)의 평균은 모든 길이-d 스트링에 대한 g(y)의 평균이다. 이 때문에, 스 크램블링 코드어는, G(m+c)가 그 평균 이하이도록 존재한다.

상기 매우 일반적인 내용은 이하의 특별한 경우에 대해 적용된다. g(y)일 경우, 스트링 y로 이웃(neighborhood)을 설명한 비트에 대해 예상 비트 오류율(BER)을 취한다. X일 경우, 모든 심볼 위치의 이웃의 세트를 취한다. 각 심볼 위치의 이웃이 C에 대해 균형 잡힌 세트인 스크램블링 코드 C인 경우, 입력 메시지 m마다, 스크램블링 코드어 c는 m+c에 대해 예상된 BER이 정확하게 랜덤한 코드어에 대한 예상 BER 이하이도록 선택된다.

그래서, 본 발명의 기초가 되는 주요 이론을 설명하는 것이 가능하다. 이웃 세트 N과, 이웃 y에 있는 비트로 이루어진 세트(심볼) 값을 고정하고, 매 중심 위치 i∈I에 대해, 이웃 i-N이 스크램블링 코드어(스크램블링 코드) C의 세트에 대해 균형 잡힌 세트라고 가정하면, 스크램블링 코드 c∈C에 대한 f(y｜c+m)의 평균은 아래의 식(이론)을 만족한다:

보다 구체적으로는, 모두 0인 스트림 m일 경우, f_x(y｜z)의 정의가 c의 X에서 모든 부분 J에 대한 합산을 야기할 때, 수반되는 다음식,

가 성립한다. 따라서, 모든 c∈C에 대한 f_x(y｜z)의 합은, C로부터 스크램블링 코드어 c 중 임의의 코드어에서 부분 J가 ｜X｜로 나누어진 주어진 스트링 y와 얼마나 일치하는지를 카운트하는 2배의 합산을 이룬다. 그러나, 주어진 부분 J에 대해, y와 일치하는 C로부터의 스크램블링 코드어 c의 수는, 상기 부분 J가 C의 균형 잡힌 세트라고 가정될 때 항상 ｜C｜q^-d이다. 모든 J에 대해 상기 출력｜C｜q^-d을 합하기와 ｜X｜로 나누기는, m이 모든 0인 스트림인 특별한 경우에 대해 상기 이론을 확립한다. 이 이론은, 임의의 스트림 m에 대해 성립한다.

이전의 문단에서, m이 임의의 가능한 스트림이면, 우리는 모든 가능한 합 s=c+m을 생각할 때, s의 모든 값은 복수(즉, ｜C｜)배가 일어날 것이다. 따라서, 그 경우에, s의 값으로부터, 우리는 c와 m의 값이라고 판단할 수 없다. 따라서, c를 사용한 선택은, m의 유일 복호성이 가능해지도록 수신기에 제공되어야 한다. 이 때문에, 이전의 문단에서 m이라고 하는 것의 역할은, 특히 청구항에서 중간 스트림 i로서 언급된다. 본 발명에 따라 제안된 것처럼 스트림 m을 스트림 i로 연장시키는 것은, s'=c+i가 대신에 사용되는 경우, 가능한 모든 스트림 s'는 한번 이하가 일어나도록 하는 일부의 중복도를 제공한다. 그래서, 이것에 의해, 상기 스크램블링된(맵핑된) 스트림 s'으로부터 c와 i의 값을 유일하게 검색할 수 있다. m부터 i까지의 확장은, 확장부의 역할이다.

도 5에는, 유도 스크램블링을 사용한 인코딩 장치의 일반적인 레이아웃을 나타낸 블록도가 도시되어 있다. 이 인코딩장치는, 사용자 데이터 스트림 m을, 사용 자 데이터 스트림 m보다 적어도 하나 이상의 심볼을 포함한 중간 데이터 스트림 i로 변환하는 확장부(150)와, 스크램블링 코드 C의 서로 다른 스크램블링 코드어 c를 상기 수신된 중간 데이터 스트림 i에 맵핑하는 다수의 맵핑부(101)를 포함한 제 1 맵핑부(100)를 구비한다. 출력, 즉 서로 다르게 맵핑된 사용자 데이터 스트림 m'은 성능 지수(FoM)의 메리트 값 v를 결정하는 다수의 처리소자(201)를 포함한 처리부(200)에 입력된다. 이들 메리트 값 v는, 최적 메리트 값 v_opt과, 이를 사용하여 최적 스크램블링 코드어 c_opt를 선택하는 선택부(300)에 제공된다. 그 후, 제 2 맵핑부(400)에서는, 최적 스크램블링 코드어 c_opt를 원래의 사용자 데이터 스트림 m에 맵핑하여, 채널 데이터 스트림으로서 채널에 출력된, 이를테면, 기록매체(50)에 저장되거나 전송선을 통해 전송된 최적으로 맵핑된 사용자 데이터 스트림 y를 얻는다. 그 채널 데이터 스트림 y(또는 여기에 포함된)를 따라서, 최적 스크램블링 코드어 c_opt에 대한 정보는 디코더에서 사용하기 위해 전송된다.

도 6에는 일례로서 처리부(200)의 처리소자(201)의 실시예가 도시되어 있다. 처리소자(201)는, 부분에 대한 제한을 하는 다수의 병렬 제한소자(202)를 구비한다. 이러한 제한소자는, 예를 들면 주어진 비트의 일시적 이웃의 일부의 공간 내에 저장되거나 전송되는 (고정된) 수의 비트를 모아서, 비트(심볼) 스트링, 또는 정수로 변형한다. 일부분 내의 비트(심볼)를 정수로 모으는 것은, 테이블을 포함하고 일부부의 모든 가능한 값(즉, 일부분 내의 심볼 값)의 성능 지수를 저장하는 메모리 내의 어드레스로서 상기 정수를 사용할 수 있으므로, 특히 하드웨어 구현에 있 어서 바람직하다. 대부분의 일반적인 경우에, 상기 성능 지수는, 서로 다른 부분에 대해 서로 다를 수 있어, 도 6은 다수의 테이블을 나타내고, 여기서, 예를 들면 부분 0(예를 들면, 심볼 스트림의 초기)은 다음의 부분 1(예를 들면, 일시적으로 나중에 또는 심볼 스트림 내에서 공간적으로 앞선다) 등과 서로 다른 성능 지수로 된다. 모든 부분의 집합은 X로 나타내고, 따라서 마지막 부분은 0부터 번호를 매길 경우 ｜X｜-1번째 부분이다.

이들 제한소자의 출력 u는, 테이블 소자의 어드레스로서 테이블 소자(203)에 공급된다. 이들 어드레스는, 일부분의 값을 포함한다. 테이블 소자는, 상기 부분의 (국부적) 성능 지수를 포함한다. 이들 테이블 소자(203)의 모든 출력은, 상기 부분의 (국부적) 성능 지수를 스트림마다 전체 성능 지수의 가중 또는 볼록 평균을 하는 평균부(204)에 제공된다. 청구항 1에 기재된 것처럼, 심볼 스트림(예를 들면, 심볼들로 이루어진 블록)의 성능 지수는, 부분 당 성능 지수의 합이다. 적절한 정규화에 의해, 상기와 같은 합은, 도 6에 도시된 것처럼 평균이 된다. 일반적으로, 최적 스크램블링 코드어 c_opt의 선택은, 일정한 정규화 인수에 의한 나누기에 의해 영향을 받지 않아서, 중요하지 않다. 어떠한 당업자에게도 부분마다(즉, 국부적) 성능 지수의 합 또는 평균을 취하는 것으로부터의 다소 약간의 편차를 고려할 수 있고 또 본 발명의 모든 이점을 얻는다는 것은 자명한 것이다. 아래의 예에서는, 제곱(square)을 사용하여 제공되고, 이때 제곱 연산이 소위 볼록(-컵(cup)) 연산인 특성을 이용한다. 따라서, 합산하거나, 또는 마찬가지로 평균을 할 때, 아래에 설명된 것처럼 볼록 평균화의 경우 등이 포함된다.

이제 본 발명을 더욱 상세히 설명하겠다. 본 발명에서는, 상기 식(이론)에서 설정된 균형 잡힌 세트 조건을 만족하는 코드 C를 사용한다. 이러한 조건은, 매 위치 i∈I마다, 이웃(i-N)이 스크램블링 코드 C의 균형 잡힌 세트(즉, 코드어 심볼 부분)이어야 하는 요구사항이 된다.

이하 본 발명의 1차원 예시를 설명한다. 먼저, 지수 세트 I를 생각하고, 모든 정수 0,1,....,K-1의 세트(여기서, K, K>2)는, 스트림 길이와, 상기 지수 세트에 관해 비트로 이루어진 세트(m₀,m₁,....m_N-1)이다. 또한, 식 (i-N)={i-1,1,i+1}(여기서, i=1,2,...,K-2)의 I의 규정된 모든 부분집합 J를 생각한다, 즉 N={-1,0,1}. 이들의 규정된 모든 부분집합 J의 집합을 X라고 한다. 또한, 3비트의 시퀀스를 정수, 고정 소수점 또는 부동 소수점 수로 맵핑하는 테이블 g(임의의 테이블 g로 할 수 있다)로 할 수 있다. 명확하게 하기 위해서, g는 3-탭 필터 출력의 거듭제곱(즉, 제곱)으로서 아래와 같이 정의된다.

상기 테이블 g의 예시는 다음과 같다.

테이블 엔트리의 수가 큰 경우에, 이와는 달리 g를 계산한다는 것은 명백하다. 특정 사용자 데이터 스트림(m₀,m₁,....m_N-1)에 대해서, 평균 거듭제곱 G는 X에 대해서 국부적 성능 지수 g의 평균으로서 정의된다.

m_-1 및 m_N에 관해 모르기 때문에, 평균 거듭제곱 G는, 필터 출력 n_i의 거듭제곱을 지 수 세트 I의 끝점(즉, n₀ 및 n_K-1)에서 포함하지 않는다.

이제, 스크램블링 코드를 정의한다. 제 1 예시로서, 반복 코드는 C로 한다. 즉, (3의 배수일 필요는 없는 길이 K-2의) 모든 스크램블링 코드어는 아래의 형태이다.

그리고, 총 2³=8개의 스크램블링 코드어가 있고 그들 각 스크램블링 코드어는 3비트(c₀,c₁,c₂)의 조합으로 유일하게 특정된다. X에서 임의의 이웃(또는 부분) J=(i-N)에 대해서, J=(i-N)에 제한된 코드어 c는 y=(c_i-1,c_i1,c_i+1)와 같고, y는 (c₀,c₁,c₂)의 일부 순열인 것을 알 수 있다. 따라서, C에 대한 g의 평균을 생각한 경우, J에 제한된 모든 코드어에 대한 국부적 성능 지수 g에 대한 합은, 모든 길이-3 이진 시퀀스에 대한 g의 평균값, 즉 0.385이다.

여기서는, 모든 코드어를 부분집합 J에 제한하는데 있어서, 길이 3의 가능한 모든 이진 시퀀스가 정확히 한번(각 J는 균형 잡힌 세트임) 일어난다는 사실을 사용하였 다. (만일의 경우에 대비하여, 모든 서브 시퀀스가 2번 일어나고, 동일한 독립변수(argument)가 성취된다) ("

"로 나타냄) 사용자 데이터 비트 스트림 m이 모듈로-2 to c 가산되어서, 맵핑된(또는 스크램블링된) 스트림

을 얻는 경우, 그 결과는 J=i-N에 의해 포함된 지수에서 모든 길이-3 이진 시퀀스에 대한 합산이어서, (예시에서 0.385) 출력은, 변하지 않는다.

이것은, (m_i-1,m_i,m_i+1)의 가산(모듈로-2)가 반전 가능 연산이기 때문에 사실에 바탕을 둔 것이다. 따라서, 이미 설명된 것처럼, 그것은,

가 된다.

이것이 의미하는 것은, c_i와 m_i를 m'_i로 조합하는 맵핑 연산으로서 심볼 알파벳의 반전 가능 연산을 수행할 수 있다. 다음에, 모든 스크램블링 코드어 c에 대한 G(m

c)의 평균의 값을, X에서 모든 J에 대해서(즉, 모든 I에 대해서, 0<i<K-1) 일부의 부분집합 J=i-N에 한정된 모든 스크램블링 코드어 c에 대한 g의 평균

의 평균으로서, 구할 수 있다. 일정한 값의 평균이 상수 값이므로, 그 결과는, 모든 스크램블링 코드어 c에 대한 G(m

c)의 평균은 상술한 상수

=0.385이고, 여기서 는

가 I에 의존하지 않는다는 사실을 이용하였다.

C에 대한 G(m

.)의 평균이 0.385라는 사실이 의미하는 것은, G(m

c_opt)가 0.385이하, 즉 스크램블링된(맵핑된) 사용자 데이터 심볼 스트림의 G(필터 출력의 평균 제곱)가 0.385이하이도록 스크램블링 코드어가 있어야 하는 C에서의 적어도 하나의 코드어 c_opt가 있다는 것이다. 이와는 달리, 상기 스크램블링된 코드어의 G가 0.385이상인 적어도 하나의 스크램블링 코드어가 있다고 결론을 내릴 수도 있다.

함수 g가, "g_i(.,.,.)"보다 위의 예시인 J마다 서로 달라지도록 될 수 있다는 것을 알 수 있다. 예를 들면, K가 짝수인 길이 K의 스트림을, 제 1 서브스트림에서의 제 1 함수(테이블)g_A와, 제 2 서브스트림에 적용하는 제 2 함수(테이블)g_B를 갖는 길이 K/2의 2개의 서브스트림으로 분할할 수 있다. 그래서, 길이 K의 전체 스트림에 대한 전체 성능 지수 함수 G의 평균은, 모든 길이-3 이진 시퀀스에 대한 g_A의 (균일한) 평균

과 모든 길이-3 이진 시퀀스에 대한 g₂의 (균일한) 평균

와의 반반의 평균과 같다.

상기 예시에서의 코드 C의 생성 행렬은 다음과 같다.

G가 (또한 일반적으로 심볼 부분이라고 불리는) 이웃에 대응하는 3개의 칼럼에 한정되는 경우, 임의의 3개의 인접 칼럼은 선형 독립이라는 것은 자명하다.

또한, 예를 들면, 본 발명의 원리,

에 영향을 미치지 않고 스크램블링 코드의 정의에 있어서 비선형성을 도입할 수 있다.

독립 선형항 "c₁"을 비트 값 "c₀c₂"의 곱에 가산하는 것은, (c₀,c₁,c₂)가 모든 가능한 8개의 조합에 대해 변화되면, 그 스크램블링 코드어가 (본 예시에서: 3개의 연속적인 지수의) 이웃(심볼 부분)에 제한되는 경우, 가능한 모든 8개의 조합은 정확히 한번 일어난다(따라서, 모든 것은 동등하게 여러 번 일어난다)는 것을 더 확실하게 한다.

유사하게, 성능 지수 G의 선형성은, 예를 들면, G에서(본 예시에서 K-2) 항의 총수에 대해 그 수가 근소하거나, 최대 또는 평균의 전반적인 크기가 여기서 설명된 것과 같은 선형 기여가 G의 작용에 우세한 범위까지 G를 왜곡시키는, 다수의 임의의 기여의 도입에 의해 왜곡될 수 있다(예를 들면, 상기 기여는, 심볼 부분 또는, 일부의 심볼 부분 등의 일부의 기여의 비선형 조합에 의존하지 않는다). 상기 제안된 방법의 이점은, 예를 들면 선형 평균 G를 가중 평균 또는 볼록 평균으로 대체되는 경우를 통해 얻는다. 이를테면, 제곱 연산은, 볼록 함수이고, 그것이 아래 식으로,

설정되는 경우, 상술한 볼록성은,

을 의미하므로, 그 함수 G는 원래의 값 g 대신에 테이블에 g의 제곱값을 저장할 수 있는 선형 상계(upper bound)를 갖고, G가 전형적인 것보다 크지 않은 맵핑된 사용자 데이터 워드가 되는 스크램블링 코드어의 존재는 본 발명을 (정확한 G의 역할을 하고 본 발명을 적용할 수 있는) 상계에 적용하는 것이 후속한다.

스트림 길이 K가 반드시 필요하지 않은 동일한 크기의 부분들의 임의의 수로 분할될 수 있고 또 본 발명이 적용된다는 것은 명백하다. 특별한 경우로서, 함수(테이블)g_i는, 모든 지수 i에 대해 서로 달라도 된다. 또한, 가중 함수가 상기 함수 g_i에 포함되는, 불균일한, 즉 가중 평균을 고려한 경우도 명백하다.

스크램블링 코드의 제 2 예시에서는, 스크램블링 코드어로서 도 7에 도시된 선형 피드백 시프트 레지스터에서 발생된 (길이 K>3의) 가능한 모든 시퀀스를 고려한다. 시프트 레지스터의 초기의 3-비트 콘텐츠를 시드(seed)라고 한다. (c₀,c₁,c₂)라고 나타낸 (길이 3의) 2³=8개의 가능한 (이진) 시드 벡터가 있다. 도 7에 도시된 시프트 레지스터 출력 시퀀스는, 선형 순환식(i+3=3,4,...,N-1), c_i+3=(c_i+c_i+1+c_i+2) mod 2가 기재될 수 있다. 상기 피드백 시프트 레지스터의 상기와 같은 시드(c₀,c₁,c₂)가 가능한 모든 길이-3 이진 시퀀스에 대해서 변하는 경우, 임의의 부분 J={i-1,i,i+1}에서, 가능한 모든 8개의 길이 3의 이진 스트링은 정확히 한번 일어난다. 따라서, 반복 스크램블링 코드에 관한 동일한 이론은 상기 경우에서처럼 이루고, 각 J={i-1,i,i+1}, i=1,2,...,K-2는 균형 잡힌 세트이다.

어떠한 테이블 g도 취할 수 있다는 것은 분명하다. 상기 예시의 변형예로서, 이웃 N은 i를 포함하지 않은, 즉 J={i-1,i+1}로서 정의된다. 그리고, 상기 예시들에서의 코드어의 수는,

c₀+c₁+c₂=0 mod 2, 이를테면,

c₁=c₀+c₂ mod 2를 설정함으로써 절반으로 될 수 있다.

이제, 위치 {i-1,i+1}와 일치하는 2-비트 입력을 갖는 함수 g(또는 보다 일반적으로는 g_i)를 생각한다. 이를테면, 채널 출력 r_i가 채널 입력 a_i(예를 들면, 스 크램블링된 사용자 데이터 스트림, 즉, a_i=m'_i)과 가우스 잡음 "noise_i"의 합: r_i=a_i+noise_i인 가산성 백색 가우스 잡음을 생각할 수 있다.

그리고, 채널 입력 a_i의 평균 제곱 값 대 평균 제곱된 "noise_i" 값의 비율인 신호 대 잡음비(SNR)는, a_i-1 및 a_i+1(즉, 일부의 스크램블링된 사용자 데이터 심볼 m'_i-1 및 m'_i+1)에 의존한다. 채널 출력 r_i에 의해 채널 입력 a_i에 관해서 전송된 예상 양의 정보(비트의 분수)가 상기 신호 대 잡음비(SNR)에 따라 대수적으로 증가하는 것을 표현하는 공지된 샤논 용량 함수,

Sh(SNR)=log(1+SNR(c_i-1+c_i+1))

를 사용하면, 쌍(c_i-1+c_i+1)과 그 결과의 SNR(이를 채널의 특성에서 알려진다고 가정한다)마다, 결과적인 샤논 용량 Sh(c_i-1+c_i+1)를 계산할 수 있다. 그리고, g(c_i-1+c_i+1)는 Sh(c_i-1+c_i+1)와 같도록 설정될 수 있고, 상기 이론을 적용하여 항상 스크램블링 코드어 c_opt가 있다는 것을 밝힐 수 있어, G, 즉 X에서 모든 이웃(i-N)(N={-1,1})에 대한 Sh(.,.)의 평균은 모든 길이-2 시퀀스에 대한 g의 균일한 평균 값 이상이고, 그 균일한 평균 값은 모든 스크램블링 코드어에 대한 G의 균일한 평균과 같다. 그래서, 보장할 수 있는 것은, 최소 유효 수의 비트가 (예측컨대, 평균적으로) 스트림마다 전송된다는 것이다. 이러한 경우에도 분명한 것은, 국부적 성능 지수 g는 격자 I에서 지수 i에 의존하게 될 수 있다.

또한, 상기 예시에서도 i번째 전송(또는 저장)을 위한 신호 대 잡음비 SNR이 i번째 이웃{i-1,i+1}에 포함되지 않은 c_i-2에 의존한 경우, 그 신호 대 잡음비는 심볼 값 c_i-2에 대한 이웃(c_i-1+c_i+1)에 포함된 심볼 값으로 이루어진 쌍의 소정 값에 대해) 최소화될 수 있어 이것은 이웃{i-1,i+1}에 포함되지 않는다. 그래서, 상기 최소화의 결과는, 국부적 성능 지수 g(c_i-1+c_i+1)로서 사용된다. 이러한 경우에, G와 g에 대해 상술한 것과 같은 이론으로, 최악의 경우의 달성 가능한 평균 샤논 용량을 보장할 수 있다. 이 경우도 스크램블링 코드어의 수 ｜C｜에 따라 증가하는 인코딩 복잡도와, 크기에 있어서 부분집합 J가 증가되므로 상기 보장된 최악의 경우의 평균 결과는 원래의 이웃 J에 포함되지 않은 부가의 심볼에 관한 영향에 대해서 최소화될 필요는 없다. 예를 들면, (c₀,c₁,c₂)에 대해 단일 패리티 검사식이 더 이상 성립될 수 없다고 가정하므로, 코드어의 수는 8까지 두 배로 되는 N={-2,-1,1}인 J=(i-N)를 사용할 수 있다.

본 발명의 주요 주제인 상기 유도 스크램블링 기술과 오류 제어코딩의 조합을 설명하기 위해서 다음의 내용을 살펴본다. 상기 나타낸 8개의 스크램블링 코드어를 갖는 반복 코드는, 전체(all-one) 벡터의 유한체 GF(2³)에 대한 배수의 세트로서 이해될 수 있다. 여기서, "전체" 중의 "하나"도 GF(2³)의 요소로서 이해되어야 한다. GF(2³)에 대해 오류 정정코드는, 전체 벡터가 코드어인 것이 존재한다. 여기서, 용어 "벡터"를 사용하면, 지수 세트 I가 1 이상의 차원인 경우는, 배제되지 않 을 것이다(그 용어 "어레이"는 - 비록 오류 제어 코딩의 범위 내에 한정되지 않지만- 보다 적절하다).

심볼간 간섭을 갖는 가산성 백색 가우스 잡음 채널일 경우에, i, i'≠i인 다른 위치에서의 출력 r_i는, 지수 i에서 입력 a_i에 대한 정보를 나타낼 수도 있다.

채널 출력의 샘플링 그리드(grid)는, 채널 입력 위치의 세트와 일치할 필요는 없다. 이를테면, 채널 출력은, 과도샘플링되어 채널 입력 심볼이 있는 채널 출력 샘플이 보다 많다.

채널 출력이 이진일 경우에, 샤논 용량은 간단히 엔트로피 항의 조합이다. 이를테면, 입력이 반반씩 0-1로 분포된 경우, 샤논 용량은 1-h(p_E)이고, 여기서의 p_E는 심볼(즉, 비트) 오류 확률이고, h(.)는 이진 엔트로피 함수 h(x)=-xlog2(x)-(1-x)log2(1-x)이다. 심볼 오류확률 p_E는, I에서 점 i의 일부의 이웃 i-N에 의존하기도 한다. 그 경우에, 본 발명의 제약을 만족시키는 스크램블링 코드에 대해서는, 오류 확률을 갖는 평균 심볼형 엔트로피가 이웃 J=(i-N)에 대한 h(p_E)의 평균보다 최악이 아닌(그 평균보다 큰) 스크램블링 코드어 c_opt가 항상 당연히 존재하게 된다. 지수 i에 의존하는 경우, X에서 모든 J에 대해 추가로 평균화할 필요가 있다.

가장 단순한 본 발명의 실시예 중 하나에서는, 국부적 성능 지수 g처럼, 심볼 오류 확률("비율")p_E 자체를, 일부의 이웃 J=(i-N)의 함수로서 생각할 수 있다. 상기 이웃의 의존 관계는, 선형 또는 비선형일 수도 있는 채널에서 일어나는 심볼 간 간섭으로 일어난다. 그리고, 스크램블링 코드 C가 본 발명의 제약을 만족하는 경우, 스크램블링 코드어 c_opt가 존재한다는 것을 보장하여 주어진 스크램블링된 사용자 데이터 심볼 스트림에 대한 상기 평균 심볼형 오류 확률은 일부의 J에서 모든 서브시퀀스에 대한 심볼형 오류 확률의 균일한 평균보다 나쁘지 않다. 또한, (예를 들면, 경우 J에서의 i의 형태는 i-N인) J에 의존 관계일 경우에, 추가로 X에서 모든 J에 대해 평균화할 필요가 있다. 이전에 주어진 실시예에서, 이진 엔트로피 함수 h(.)는 이러한 실시예와 비교하여 보다 큰 p_E의 기여도에 관계되는 보다 작은 p_E에 대한 기여도를 증폭한다.

반복 코드가 -코드의 단순함으로 인해 이로운- 스크램블링 코드로서 사용되는 경우에, "채색"을 사용하여 코드를 구성할 수 있다. 그리고, 정확한 것은, I의 일부의 부분집합 J에 포함된 모든 지수는 모두 뚜렷한 색을 갖는다는 것이다.

반복 코드에 의한 1차원 예시에 대해, 채색은 (0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,....)이다.

본 예시에서, X에서의 임의의 J는 3가지 서로 다른 색을 갖는다.

6각형 격자로 사용하도록 설계되는 반복 스크램블링 코드일 경우에 대한 실시예를 나타낸다. 중심 점 및 그것의 6개의 이웃으로 하고, 7개의 요소 6각형 클러스터를 함께 구성하고, (또한 사용자 심볼 부분이라고도 하는) 클러스터의 그 7개의 요소(심볼 또는 비트) 각각은 (7개의 요소 각각에 서로 다른 라벨을 할당하는 것과 동등한) 서로 다른 색으로 주어진다. 검증된 것은, 6각형 평면이, 상기 세트 로 타일로 될 수 있다(즉, 타일로 분할될 수 있다)는 것이다. 그 제 1 실시예는, 다음의 테이블에 도시되어 있다:

서로 다른 각 색은, 다수의 변형이 존재하는 테이블에 있는 서로 다른 수(라벨)로 심볼화된다. 이러한 상기 채색의 특별한 실시예에서, 색 수는, 하나가 2행 아래로 가는 경우 2개의 모듈로 7에 의해 증가한다. 주목하는 것은, 정확한 6각형 격자에서와는 달리, 최근접 이웃에 대한 수직 및 수평 거리가 본 테이블에서는 동일하지 않다는 것이다.

스크램블링 코드어 c_opt를 구하는 직접적인 방식은, 모든 스크램블링 코드어의 (부분집합)에 대한 스트림 당 성능 지수 함수 G의 값을 구하는 것이다. 그 후, 계산상의 복잡도는, 스크램블링 코드어의 수｜C｜와 스트림 길이 K의 곱에 비례한다.

c_opt를 구하는 다른 방식은, 다음과 같이 색당 하나의 히스토그램, 히스토그램의 수를 사용하는 방식이다. 그 후, 그 히스토그램을 카운트하는 계산상의 복 잡도는, 스트림 길이에 비례한다. 스트림 길이가 크다고 하면(예를 들면, 약 수천 비트), 나머지 계산상의 복잡도는 일반적으로 무시 가능하다. 그래서, 계산상 복잡도는, 스크램블링 코드어의 수, 즉｜C｜의 대략 계수만큼 감소된다.

도 8에는 다수의 히스토그램을 사용한 인코더의 일반적인 레이아웃이 도시되어 있다. 일부의 부분, 특히 최적의 메리트 값 v_opt를 선택하고 여기서는 별도의 생성부(301)가 설치된 최적의 스크램블링 코드어 c_opt를 생성(또는 선택하는) 선택부(300)와, 그 최적의 스크램블링 코드어 c_opt를 사용자 데이터 스트림 m에 맵핑하는 제 2 맵핑부(400)가 도 5에 도시된 것과 유사하거나 또는 아주 동일하지만, 인코더의 제 1 부분은 서로 다르다.

인코더는, 아래에 설명되는 것처럼 다수의 히스토그램 H를 계산하기 위한 하나 이상의 카운트 소자를 갖는 카운트부(500)를 구비한다. 이들 히스토그램 H는, 다수의 히스토그램 변환소자(601)를 갖는 히스토그램 변환부(600)에 제공될 것이다. 모든 스크램블링 코드어가 서로 다르므로, 여기서는 스크램블링 코드어 c의 가능한 각 선택은 히스토그램마다 서로 다른 변환을 이룬다. 따라서, 스크램블링 코드어(즉, n=｜C｜로 나타낸 도면에서 ｜C｜)가 있는 만큼의 히스토그램의 세트의 변형이 있다. 결국, 이것은 3개의 이진 심볼(비트)를 포함한 부분에 대한 1차원 케이스에 대한 예시로 설명된다.

도 9에는 카운트부(500)의 실시예가 보다 상세히 도시되어 있다. 그 카운트부는, 부분에 대한 제한을 위한 다수의 병렬 제한소자(501)를 구비한다. 이들 제한 소자(501)의 출력 u는, 하나 이상의 카운트부(502)에 제공되어 이 카운트부에서 그 부분의 값에 관한 발생 빈도를 카운트한다. 이들 카운트 소자(502)의 출력은, 히스토그램 H이다.

이를테면, 일 부분이 1차원 비트 스트림으로부터 3개의 연속적인 비트를 포함하는 예시에서는, 일부분의 2³=8개의 가능한 콘텐츠, 즉 스트링 000,001,010,...,111이 있다. 이들 스트링은, 정수 0,1 내지 7로 식별될 수 있다. 일반적으로, 서로 다른 부분은, 중첩할 수도 있다(즉, 공통으로 심볼 위치를 가질 수도 있다) 모든 부분 X의 집합은, 부분집합 내의 부분이 중첩되지 않도록 부분집합의 수 -본 예시에서는 3-으로 분할될 수 있다. 예를 들면, 상기 부분의 집합 X의 제 1 부분집합은, 형태 {i-1,i,i+1}의 지수를 갖는 모든 부분을 포함하고, 이때 그 부분집합은 3의 배수이다. 상기 집합 X의 제 2 부분집합은 i가 3의 배수 플러스 1인 상기 형태의 모든 부분을 포함한다. 상기 집합의 제 3 부분집합은 i가 3의 배수 플러스 2인 모든 부분을 포함한다. 분명한 것은, 일반적인 경우에 대해 설명된 것처럼, 동일한 부분집합 내의 서로 다른 부분은, 공통으로 지수를 갖지 않는다(즉, 공통으로 심볼을 갖지 않는다). 이것은, 도 9에 의해 설명된다: 즉 부분의 집합 X의 부분집합마다, 히스토그램은, 일부분 내에서 가능한 심볼 스트링의 발생 빈도를 나타낸다. 이러한 방법은, 1차원 경우에서 사용될 수 없지만, 예를 들면 설명된 6각형 격자 예시일 경우에도 결과적으로 사용될 수도 없다. 그 경우에, 모든 부분의 집합 중 A=7개의 서로 다른 부분집합이 있고, 이때, 단일 부분집합 내의 부분은 중 첩되지 않고 (2차원) 반복 코드어의 선택에 의해 유일하게 변형된다.

이제, 도 8에는, A=3이고, 3개의 히스토그램이 생성된다. 제 1 히스토그램은, 각 8개의 가능한 값 000,001,...111이 집합 X의 제 1 부분집합에서 얼마나 자주 일어나는지를 카운트한다. 제 2(제 3) 히스토그램은, 집합 X의 제 2(제 3) 부분집합에 대해 유사하게 카운트한다. 또한, 반복 코드를 사용한다고 가정한다. 반복 코드만큼 단순한 코드의 사용을 통해, 상기 집합의 제 1, 제 2 및 제 3 부분집합으로부터 3개의 타입의 부분 각각이 반복 코드로부터 특별한 스크램블링 코드어의 선택에 의해 유일한 방식(즉, 부분집합 당 유일한)에서 영향을 당연히 받는다. 상기 집합의 각 부분집합마다, 스크램블링 코드어의 각 선택은, 그 부분집합에서 일부분의 값의 서로 다른 변환을 의미한다. 도 8에 도시된 것처럼, 스크램블링 코드어, 즉 n=｜C｜와 같은 수의 A(본 예시에서는 3) 히스토그램의 세트에 관해 작동하는 변환부가 있다. 따라서, 총 A｜C｜(본 예시에서는 3｜C｜)에서, 개개의 히스토그램이 변환된다. 상기 집합의 부분집합 당 상기 변환된 히스토그램은, 전체 히스토그램에 대한 조합된 히스토그램으로 합산된다. 그래서, 히스토그램의 변환된 세트는, 충분한 정보를 제공하여 중간 심볼 스트림과 특별한 스크램블링 코드어를 서로에 맵핑하는 것인 심볼 시퀀스에서의 부분(000,001,..,111)의 발생 빈도를 계산한다. 이것은, 예를 들면, 도 6에서와 같은 테이블을 이용하여 수행된 것과 같은 일부분의 성능 지수의 테이블 값은 모든 테이블에 대해 동일하다고(즉, 성능 지수는 시간적으로 또는 공간적으로 변화하지 않는다고) 가정한다. 히스토그램(카운팅)의 정의와 부분당 성능 지수면에서의 전체 선능 지수의 정의의 모두가, 가산("합산")에 기 초한다는 것이 공통이라는 것을 주의한다. 따라서, 국부적인 부분 당 성능 지수는, 가능한 모든 부분(000,001,..,111)의 성능 지수가 공지될 때 계산될 수 있고, 이들 부분 값의 각각이 상기 3개의 변환된 히스토그램의 합산에 의해 나타내어진 것처럼 상기 맵핑된 심볼 스트림에서 얼마나 자주 일어나는지가 계산될 수 있다. 다음에, 성능 지수는, 스크램블링 코드어의 가능한 선택마다(n=｜C｜) 계산될 수 있고, 최적의 코드어 c_opt가 중간 심볼 스트림 i로 최종 맵핑(예를 들면, 비트스트림일 경우에 가산 모듈로 2)을 위해 선택되어 사용될 수 있다.

도 5의 방법은 (｜C｜K)의 복잡도를 갖고, 도 8의 방법은 단지 K의 복잡도를 갖는다. 예를 들면, 6각형 격자에 대해 주어진 예시에서처럼 ｜C｜의 스크램블링 코드의 크기가 2⁷=128인 경우, 이는 현저한 이점을 갖는다.

상기에서는, I의 부분집합 J의 집합 X, 각 크기 d, 워드 z 및 스트링 y=(y₁,y₂,...,y_d)에 대해, f_x(y｜z)는, y가 J에서의 z와 일치하는 X에서의 세트 J의 분수로서 정의하였다. J가 형태(i-N)를 갖는다, 즉 중심 지수 i로 이동된 일부의 이웃 N의 버전이라고 가정한다. 이제, 1개의 색에 대해서, f_x(y｜z,l)를 X에서의 세트 J=i-N의 분수라고 하고, 이때 i는 y가 J에서의 z와 일치하는 색 l을 갖는다. 주목할 것은, f_x(y｜z,l)가 모든 색 l에 대해서 합산되는 경우, f_x(y｜z)가 수신된다는 것이다.

G(m

0)=G(m)의 값을 즉, 모든 제로인 코드어 0에 대해 구하는 경우, 히스토 그램 f_x(y｜m,l)의 세트의 정보는, f_x(y｜m,l)의 정보가 f_x(y｜m)의 정보를 의미하므로 충분하다. 그리고, G(m)=∑f_x(y｜m)g(y)는, y벡터의 수, 즉 q^d에 비례하는 일의 양으로 계산될 수 있다.

이동(shift) 불변 이웃 개념, 즉 J=i-N에 의해, 중심 지수 i가 색 l을 갖는 것이 공지된 경우, J에서의 (다른) 지수의 색도 공지된다는 것을 주목할 수 있다. G(m

c)의 값을 구한다고 가정하고, 이때 c₀=1,c₁=0, c₂=0, 색 l은 c₁("c sub l")의 스크램블링 코드어에서의 비트 값에 해당한다고 가정한다. 그리고, 중심 색 l=0을 갖는 히스토그램에 대해, 그 중심 비트가 그 중심 지수에서의 메시지 비트에 c₀=1을 가산하는 것으로 인해 반전되는 것을 안다. 이러한 가산은 히스토그램 f_x(y｜m

c,0)=f(y'｜m,0)을 변환하고, 이때 y'와 y는 중심 비트에 해당하는 비트 값에 있어서 서로 다르다.

그리고, 중심 색 l=1을 갖는 히스토그램에 대해서, 그 중심 비트의 좌측으로의 비트가, 그 좌측 이웃에서 메시지 비트에 c₀=1을 가산하는 것으로 인해 반전된다는 것이 공지되어 있다. 이러한 가산은, 히스토그램 f_x(y｜m

c,0)=f_x(y"｜m,0)을 변환하고, 이때, y"와 y는 중심 비트의 비트 좌측에 해당하는 비트 값에서(즉, 지수 i'=i-1에서, 여기서 i는 중심 지수임) 서로 달라도 된다.

그리고, 중심 색 l=2를 갖는 히스토그램에 대해서, 그 중심 비트의 우측으로 의 비트가, 그 우측 이웃에서 메시지 비트에 c₀=1을 가산하는 것으로 인해 반전된다는 것이 공지되어 있다. 이러한 가산은, 히스토그램 f_x(y｜m

c,0)=f_x(y'''｜m,0)을 변환하고, 이때, y'''와 y는 중심 비트의 비트 우측에 해당하는 비트 값에서(즉, 지수 i'=i+1에서, 여기서 i는 중심 지수임) 서로 달라도 된다.

주어진 스크램블링 코드어에 대한 상기 방식의 모든 히스토그램 f_x(.｜m,l)는 f_x(.｜m

c,l)의 순열에 의해 계산될 수 있다. 명백한 것은, 이것이 주어진 예시의 코드어에 대해서가 아니라 임의의 스크램블링 코드어 c에 대해 성립한다는 것이다. 그 후, G(m

c)=∑f_x(y｜m

c)g(y)는, y벡터의 수, 즉 q^d에 비례하는 일의 양으로 계산될 수 있다. 스크램블링 코드어마다, 히스토그램을 순열하기 위한 총 일 양은, y벡터의 수(즉, q^d)의 색수배에 비례한다(이하이다). 후자의 곱이 스트림 길이 K보다 작은 경우, 후자의 기술은 G(m

c)의 값을 직접 구하는 것에 대해 계산상의 자원을 절약한다.

도 10은 서로 다른 색(또는 라벨)을 상기 테이블에 따라 채널 심볼에 할당하는 6각형 격자에 관한 채널 데이터 스트림의 부분을 나타낸다. 크로스 해칭은 제 1 심볼 값(예를 들면, 비트 값 '1')을 의미하고, 해칭이 없는 것은 채널 심볼의 제 2 심볼 값(예를 들면, 비트 값 '0')을 의미한다.

이러한 타일링(tiling)은, 7-세트에 관해 초기에 정의된 채색을 전체 6각형 격자까지 확대한다. 세트(타일) 내에, 단일 패리티 검사 코드(즉, 6개의 정보비트 와 1개의 패리티 비트)를 정의하는 것이 바람직하다. 채색을 사용하여, 이 코드는 타일마다 반복되어, 2⁶=64 코드어를 갖는 긴 반복코드가 생성된다. 상기 단일 패리티 검사식을 이용하여, 최대 코드어수는, (주어진 메시지 m에 대한) 성능 지수가 2⁷ 내지 2⁶에서 구해지도록 감소되어, 인코딩의 복잡도를 감소시킨다. 이러한 감소는, 주어진 입력 위치 i에서의 국부적 성능 지수 함수(g)가 위치 i 자체에서의 채널 입력에 본질적으로 의존하지 않고, 위치 (i-N)에서의 그 이웃에만 의존하는 경우만 선택되고, 여기서, 미분 이웃 지수 N의 세트는 제로 벡터를 포함하지 않는다. 검증되어야 하는 것은, 상기 반복 코드에 대해, 임의의 이웃(i-N)은 정확히 6개의 서로 다르게 채색된 비트를 포함하고, 정보 세트(즉, 심볼 부분)이다. 이것은, 2차원 코드 예시에 대한 상기 이론을 위한 코드의 구성을 종료한다.

아래의 문단은, 상기 계산에 대한 동일한 히스토그램 기반 접근법의 보다 일반적인 처리를 나타낸다.

이하에서, I에 대한 한번의 합산을 필요로 하고(사전처리단계) c마다 히스토그램을 조작하는 f(y｜m+c)의 값을 구하는 다른 방법을 설명하겠다. 스크램블링 코드는 상술한 것처럼 타일링에 의거한 격자 채색을 사용하여 구성된다고 가정한다. 채널 입출력의 격자의 지수 세트 I는, 공통 원소를 갖지 않는 부분집합 I_u, u∈U로 분할될 수 있다. u∈U마다, 경험적 분수 f_u(y｜s), s=m+c는,

f_u(y｜c)s)=l/n｜{i∈I_u｜ 모든 j∈N에 대해,y_j=s_i-j}｜로 정의되고,

여기서, n은 I의 크기이다. 이전에 정의된 경험적 분수는, 새로운 경험적 분수로부터 모든 색에 대한 간단한 합산,

f(y｜s)=∑_u∈Uf_u(y｜s)

을 이용하여 계산될 수 있다. 스크램블링 코드는, 임의의 스크램블링 코드어에 대해서, 동일한 색(즉, 동일한 라벨)의 격자점이 동일한 코드어 심볼 값을 갖는 특성을 갖는다. 이제, j∈N일 경우, 타일링의 정의는, {i-j/i∈I_u로부터의 모든 점의 색(라벨)이 동일한 이웃 세트 j∈N에서의 고정된 지수를 의미한다. C가 동일한 색의 점에서 일정하므로, i∈I_u마다 c_i-Δj=z_j(u,c)가 성립하는 심볼 값 z_j(u,c)이 있다. 이 때문에, f_u(y｜m+c)=l/n｜{i∈I_u｜ 모든 j∈N에 대해,m_i-j=y_j-z_j(u,c)}｜가 성립한다. 이 때문에, z(u,c)에 의해 (z₁(u,c),z₂(u,c),...,z_n(u,c))로 나타내는 경우, f_u(y｜m+c)=f_u(y-z(u,c)｜m)이 성립한다. 이 식은, 다음과 같이 사용될 수 있다. 먼저, 메시지 m이 스크램블링된다고 하면, 모든 색 u와 길이 a의 모든 q-ary 벡터에 대해 양 f_u(y/m)이 계산된다. 이것은 모든 격자점에 대한 합산을 포함한다. 따라서, 색 u마다 그리고 코드 c∈C마다, f_u(y｜m+c)는 상기 식을 사용하여 계산된다. 주목해야하는 것은, z_j(u,c)의 j번째 엔트리는, 임의의 i∈I_u에 대해 위치 i-Δ_j의 값과 동일하다는 것이다.

반복 구성을 사용하므로, GF(2⁷)에 대한 오류정정 코드가 사용되면, 하나의 심볼에서 서로 다른 색을 갖는 비트를 모을 때, 상기 제안된 스크램블링 코드는 GF(2⁷)로부터 임의의 계수와 곱해진 모두 1인 코드어로 구성된다. GF(2¹⁴)에 대해, 2개의 타일은, 심볼로 분할된다. 7 및 그것의 배수가 심볼 크기로서 바람직하지 않은 경우에, 상기 테이블에 나타낸 채색의 구성은, 단일 행(row), 예를 들면 0,1,...,7의 수에 관해 반복하여 확장될 수 있고 GF(2⁸)를 사용할 수 있다.

아래에서는, 관례대로, 제안된 유도 스크램블링 기술과 8-비트 바이트에 관해 연산하는 오류 제어 코드와 조합하게 되는 경우 보다 바람직한 특성을 갖는 8-채색이 나타내어져 있다.

이러한 6각형 격자의 8-채색은, 아래에 설명될 오류 제어 코딩과 조합을 만족시키는 매우 바람직한 특성을 갖는다. 주목하는 것은, 스크램블링 코드어 길이의 선택에 대해, 대부분의 논리적 선택은 광학 저장 채널 후에 디코딩되는 제 1 오류 정정 코드의 스트림 크기와 (근사하게) 중첩되게 하는 것이다. 그 후, 상기 제안된 유도 스크램블링 기술은, 그 스트림에서의 예상된 비트 오류의 수를 "정확하게"(즉, 균일하게) 랜덤 입력 데이터에 대한 "전형적인" 예상 값으로 한정한다.

(2차원 경우에 대한) 도 11과 (1차원 경우에 대한) 도 12에는, 서로 다른 스크램블링 코드어를 사용자 데이터 스트림에 맵핑하는 것이 도시되어 있다. 도 10에 도시된 것처럼 이미 라벨이 붙여진 도 11에는, 사용자 데이터의 2차원 스트립 S의 일부가 도시되어 있다. 중심 심볼 b0과 그 중심 심볼 b0 둘레의 6개의 최근접 이웃 심볼 b1-b6로 이루어진 사용자 심볼 부분을 U로 나타낸다. 좌측에는, 라벨이 붙여진 사용자 데이터에 관해 맵핑된 서로 다른 스크램블링 코드어 c의 서로 다른 코드어 심볼 부분 cu₀-cu_N-1이 나타내어져 있다. 스크램블링 코드어 c는, 다수의 동일한 코드어 심볼 부분 cu로 이루어지고, 각 코드어 심볼 부분은, 고정된 수의 코드어 심볼을 갖는다. 맵핑을 보다 상세히 설명하기 위해서, 이를테면, 중심 비트 b0이 제 1 라벨 10으로 붙여지고, 주위 비트 b1-b6이 라벨 l1-l6으로 붙여진다고 가정한다.

맵핑 단계의 첫 번째 반복에 있어서, 제 1 코드어 심볼 부분 c₀는, 스트립 S의 모든 사용자 심볼 부분 U에 맵핑된다. 그래서, 이를테면, 제 1 코드어 심볼 부분 cu₀의 제 1 코드어 심볼 cu₀₀(=0)은, 스트립 S에 존재하는 모든 라벨 10 상에 맵핑된다. 그 후, 제 1 코드어 심볼 부분 cu₀의 모든 다른 코드어 심볼 cu₀₁-cu₀₆은, 스트립 S에 존재하는 대응한 라벨 l1-l6 상에 맵핑된다. 제 1 반복에서는, 비트-스 트링 "0000000"을 모든 사용자 심볼 부분 U에 할당한다.

또 다른 반복에서는, 동일한 방식으로 사용자 데이터 스트림 상에 다른 코드어 심볼 부분 cu₁-cu_N-1를 맵핑하고, 예를 들면, 제 2 반복에서는 모든 라벨 10 등에 맵핑하여, 그 비트-스트링 "0000001"를 모든 사용자 심볼 부분 U에 할당한다.

각 반복시에, 상기 맵핑된 심볼 코드어 심볼 부분의 코드어 심볼은, 기초의 사용자 심볼 값에 (이진의 경우 모듈로 2에서; M-ary 경우의 모듈로 M에서) 가산된다. 그 후, 각 반복시에, 성능 지수(FoM)의 메리트 값을 결정한다.

도 12에는, 각 사용자 심볼 부분이 5개의 연속적인 심볼을 포함하는 1차원 사용자 데이터 스트림의 부분이 도시되어 있다. 도 11에 도시된 2차원 경우에 대해 설명된 것처럼, 서로 다른 스크램블링 코드어 c의 서로 다른 코드어 심볼 부분 cu₀-cu_N-1는, 5개의 서로 다른 라벨 l0-l4에 의해 이전에 라벨이 붙여진 사용자 데이터 스트림의 모든 사용자 심볼 부분에 따로따로 맵핑된다. 상기 BER은, 비트 검출 후 공지될 뿐이지 인코더에는 공지되어 있지 않다. 그래서, 용어 "BER"을 사용하는 경우, 일부의 채널 모델을 사용하여 그 BER의 예측을 의미한다. 격자 지수 세트 I에서의 위치 i의 비트 오류 이벤트에 관한 상기 예측은, 인접 위치 i-N={i-n｜n∈N}에 의존한다. 위치 i에서의 비트 오류 확률의 계산에 있어서, i-N 외측의 위치의 심볼 값은 임의로(예를 들면, 모두 제로) 선택되어도 되거나, 모델에 포함되지 않는 비트 위치에 대한 상기 예상 BER의 "최악의 경우"를 찾기 위해 다수의 가능한 조합에 대해 변화되어도 된다.

유도 스크램블러의 태스크는, "양호한" 스크램블링 코드어 c*를 찾는데 있고, c*=arg min_c∈CBER(m+c)이다.

그래서, 유도 스크램블러는 인코더이고, 그 스크램블링 코드어 c*를 입력 어레이("메시지" 또는 "사용자 데이터 스트림")에의 가산이 인코딩 동작으로서 보여질 수 있다. 완벽함을 위해, 언급된 것은, 유도 스크램블러의 입력 데이터가 실제로 다른 인코딩 동작의 출력이어도 된다는 것이다. 범용성을 위해, 또 언급된 것은, 고려될 필요가 있는 코드어의 수가 부분집합 S⊂C까지 감소될 수 있다는 것이고,

여기서,

따라서, 코드어 c'∈S가 존재하여,

말로는, 알 수 있는 것은, 스크램블링 코드 C의 분수 α<1를 포함하는 부분집합 S에 대한 BER(c+m)의 최소값만이 검색되는 경우, 이것은 보장된 예상 비트 오류율의 최대 1/α 증가하는 비용이 든다. 이 때문에, m이 변경되지 않은 경우, 즉 그 검색 을 모든 제로 워드만으로 이루어진 부분집합 S에 한정되는 경우, BER은 전체 코드에 대한 평균 BER의 최대 분수 1/α=64배 크다.

상술한 것처럼, 유도 스크램블링 검색의 간단한 구현은, 가능한 모든 스크램블링 코드어 c에 대해 BER(m+c)의 값을 구하고, BER(m+c^*)가 최소인 그 코드어 c^*를 뽑는다. 후보 스크램블링 코드어 c에 대한 BER(m+c)의 값을 간단하게 구하는 것은, 모든 y에 대한 f(y/m+c)의 값을 구하는 것을 수반한다. 후보 스크램블링 코드어 c마다, 전체 격자 지수 세트 I에 대한 합산을 포함하고, 그 합산은 코드어 길이 K와 동일한 크기를 갖는다.

분명한 것은, C로부터의 코드어의 품질을 검사하는 순서가 상관없다는 것이다. 이로부터 (그레이 코드형 방식을) 고려한 코드어 d로부터의 벡터 z(u,d)의 고려하에 코드어 c에 대한 벡터 z(u,c)를 비교적 간단하게 얻도록 C로부터 워드를 정렬함으로써 이점을 얻을 수도 있다.

상술한 것처럼, 최악의 경우 BER은, 가능한 정보 스트링마다 적절한 인코딩 양자 택일을 선택함으로써 평균의 경우 BER을 초과하지 않도록 만들 수 있다. 이하에서는, 이것과 오류 정정 코드를 조합하는 방법을 설명하겠다.

상기 문제점을 알기 위해서, 메시지 스트링 m이 오류 정정 코드 D로부터 워드 d(m)으로 인코딩된다고 가정한다. 그 워드 d(m)에다가, 스크램블링 코드 C로부터의 적절한 워드는 가산하고, 즉 워드 c(d(m))라고 하여서, 결국 워드 d(m)+c(d(m))는 예를 들면, 매체에 기록된 채널에 출력될 것이다. 이 때문에, M은 인코딩될 수 있는 가능한 모든 스트링의 세트를 나타내는 경우, 기록될 수 있는 워드의 세트는,

X={d(m)+c(d(m))｜m∈M}과 동일하다.

그 문제점은, X의 오류 제어능력이 D의 능력보다 상당히 나빠도 되는 것이다.

확실한 것은, C와 D가 강력한 선형 오류 정정 코드 E에 포함되고 C와 D가 보통 모두-제로 워드를 갖는 것을 확보함으로써, 세트 X가 좋은 오류 제어 능력을 갖는다는 것이다. 이러한 경우에서처럼, X는 E에 포함되고, d(m)+c(d(m))를 검색하기 위한 E에 대한 임의의 디코딩 알고리즘이 사용될 수 있고, 이러한 m으로부터 검색될 수 있다. 2차원 코드의 경우에 대해 다소 명백한 예시를 한다. 실제로, 이러한 예시는, US 5,671,236 및 US 5,845,810에 기재된 것과 같은 소위 람다-트릭을 사용하여 스크램블링 코드와 오류 정정의 조합을 증명한다.

E를 [n k] 코드라고, 이 코드의 심볼은 8-비트 바이트이다. 즉, E로부터의 워드는 n 바이트로 이루어지거나 또는, 동등하게 8n 비트로 이루어진다. E가 1들만으로 이루어진 코드를 포함한다고 가정한다. 그 후, 선형성에 의해, 바이트 x마다, E는 x의 n-배 반복으로 이루어진 워드를 포함한다.

코드 C⊂E는, 64 워드로 이루어지고, 각각은 n 바이트를 포함한다. 다음과 같이 기재된다: 동일한 색의 비트는 동일한 값을 갖고; 비트가 "1"로 설정된 {0,1,2,3}로부터의 색의 수가 짝수이고, 그것은 비트가 "1"로 설정된 {4,5,6,7}로부터의 색의 수이다. 즉, C는 형태(x,x,...,x)의 모든 워드로 이루어지고, 여기서 x=(x₀,x₁,...,x₇)이어서,

및

이제, 상기 테이블에서 8색을 갖는 6각형 격자의 채색을 고려할 것이다. i=0,1,...,7일 경우, 색 i로 채색된 점의 이웃의 색은, 다음과 같다(여기서 색 지수는 모듈로 8을 판독하는데 있다):

여기서 알 수 있는 것은, 각 이웃의 6개의 점은, 뚜렷한 색으로 채색된다는 것이다. i로 채색된 점의 이웃에서의 2개의 미싱(missing) 색은, i와 i+4이다. 이 때문에, 임의의 이웃으로부터의 6개의 점은, {0,1,2,3}으로부터의 3색과 {4,5,6,7}으로부터의 3색으로 채색된다. 이러한 내용과 C의 정의를 조합하면, 알 수 있는 것은, 임의의 이웃에서, 2⁶ 가능한 비트-조합 각각이 C로부터의 워드 중에서 한번 일어나는 것이다. 완벽함을 위해, 상술한 것들에 유사한 x에 관한 제한이 적절한 코드 C를 산출하는 것을 언급한다. 실제로, 임의의 a∈{0,1}와 임의의 b∈{0,1}에 대해, C_a,b를 형태(x,x,...,x)의 모든 워드로 이루어진 코드이고, 이때 x=(x₀,x₁,...,x₇)이어서,

및

임의의 a 및 b에 대해, C_a,b는 원하는 목적을 위해 적절한 코드이다는 것을 알기가 쉽다.

이제, 도 13에 도시된 간단한 흐름도를 사용하여 인코딩을 설명한다. G를 상부 행에서의 1들만을 갖는 E에 대한 생성 행렬이라고 한다. k-1 바이트로 이루어진 스트링은, n 바이트의 스트링으로 인코딩된다. 인코딩은, 2단계로 이루어진다.

S11: m을 코드어로 인코딩한다 d(m)=(0,m)G

S12: x₀,x₁,x₂,x₃과 x₄,x₅,x₆,x₇ 양쪽에서 1들의 수가 짝수인 적절하게 선택된 바이트 x=(x₀,x₁,...,x₇)에 대해, m을 d(m)+(x,x,...,x)로 인코딩한다.

주목할 것은, m이 코드 E로부터의 워드로 인코딩된다는 것이다.

도 14의 간단한 흐름도에 도시된 디코딩은, E를 위한 디코더로 쉽게 행해질 수 있다. 수신된 채널 워드 r을 ECC 디코딩한 후의 워드(S21)는 w=(w₁,w₂,...,w_n)와 같다. 그 후, 상기 디코딩된 메시지 m은 아래식,

w=(w₁,w₁,...,w₁) +(0,m)G

로부터 분리단계(S22)와 디맵핑 단계(S23)에 의해 구해진다. G가 일반적으로 바로 그 경우처럼, 식별자 행렬을 포함하는 경우, m은 간단히 식별자 행렬에 대응한 위 치에서의 바이트의 시리즈와 동일하다.

도 15는 본 발명에 따른 디코더의 블록도를 나타낸다. 또한, 본 도면은, 최좌측 k+1위치에서 체계적인 (n,k+1) ECC 코드(코드어 길이 n, 치수 k+1)의 경우에 대한 분리 및 역맵핑 단계를 나타낸 것이다. 스크램블링 코드어의 선택은, 최좌측 정보 심볼을 통해 밝혀진다. 그 메시지 m은 연속적인 k개의 정보 심볼로 이루어진다. 분리부(800)의 하나의 출력, 즉 (w₁,w₁,...,w₁)은 (반복 코드 C로부터의) 스크램블링 코드어를 나타낸다. 분리부(800)의 다른 출력은, 중간 시퀀스 i, 즉 (0,w₂-w₁,...w_n-w₁)이고, ECC 디코더(700)의 출력(w₁,w₂,...,w_n)으로부터 스크램블링 코드어(w₁,w₁,...,w₁)를 감산한 결과이다. 끝으로, 역맵핑부(900)는, 길이 k의 메시지 심볼 시퀀스 m을 얻기 위해서, 단순히 ECC 패리티 심볼뿐만 아니라, 중간 시퀀스 I로부터의 최좌측 심볼을 제거한다.

이러한 방법을 적용하도록, 필요한 것은, 코드 E가 모두-1의 워드를 포함한다는 것이다. 이것은 E가 길이 K=q-1의 F_q에 대한 리드-솔로몬 코드인 경우 정확하지만, q-1보다 작은 길이 K의 리드-솔로몬 코드에 대해서는 정확하지 않다. 소수의 변경에 의해, [n,k]단축 리드-솔로몬 코드 E는, 모두 1인 워드를 포함한 코드로 변환될 수 있다. 실제로, a=(a₁,a₂,...,a_n)를 E로부터의 워드로 하여, i=1,2,...,n에 대해서, a_i≠0은 항상 존재한다. 일반화된 리드-솔로몬 코드 E_a는, E_a={(c₁/a₁,c₂/a₂,...,c_n/a_n)∈E}로 나타낼 것이다. E가 a를 포함하므로, 모두 1인 워 드는 E_a에 있다. 2개의 보다 명백한 방법은, E에 대한 인코더 Ψ가 배치된다고 가정하는, E_a에서의 워드로 정보 바이트의 스트링을 인코딩하도록 존재한다.

제 1 대안은, i번째 심볼을 a_i로 나누어서 후속된 정보 스트링을 Ψ에 공급하는데 있다. 제 2 대안에 대해서, Ψ이 시스템적 인코더라고 가정한다. 위치 i에 대응한 정보 심볼은, a_i와 곱해질 수 있고, 그 변경된 정보 스트림은 Ψ에 공급될 수 있다. Ψ에서 생성된 패리티 심볼은, j의 적절한 값에 대해 a_j로 나누어지고; 그 정보 심볼은, 변경되지 않게, 즉, a_i와의 곱셈없이, 기록된다.

분명하게, 인코딩 방식이 디코더에게 공지되어야 한다. E_a에 대한 디코딩은, 수신된 워드의 i-번째 심볼과 a_i를 먼저 곱하고 나서, E를 위한 디코더를 적용하여서 행해질 수 있다. 상기 E로부터 얻어진 워드 i-번째 심볼을 a_i로 나누어서, E_a에서의 대응한 워드를 얻는다. 정보 심볼에만 1을 삽입하고, 체계적인 방식으로 인코딩을 행한 경우, 나누기를 할 필요는 없다.

중심 비트도 이웃에 포함되어야 하는 경우, 상술한 방법의 결과로부터의 간단한 변경을 사용할 수 있다. 스크램블링 코드로서 상기 형태(x,x,...,x)의 모든 워드의 세트를 사용하기를 제안하고, 이때, x=(x₀,x₁,...,x₇)는 "1"로 설정된 비트의 짝수를 포함한다. [8,7,2] 코드에서의 임의의 7개의 위치가 균형 잡힌 세트를 구성하고, (중심 비트를 포함한) 이웃에 있는 모든 비트가 서로 다른 색을 가지므 로, 상기 이론은 그래도 적용될 수 있다. 주목해야 하는 것은, 이러한 경우에, C는 2⁷=128 워드로 이루어진다는 것이다.

US 5,671,236 및 US 5,854,810에 기재된 것과 같은 Denissen 및 Tolhuizen의 상기 소위 람다 트릭을 사용하면, 스크램블링 방법은, 모두 1인 워드를 포함하는 바이트 배향 오류 정정 코드와 효율적으로 조합될 수 있다. 리드-솔로몬 코드의 간단한 변경은, 모두 1인 워드가 그 변경된 코드에 있도록 하는 것을 제안한다. 상기 제안된 본 발명의 스크램블링 코드가, 모두 하나의 코드어의 배수로서 생각될 수 있다는 사실은, "람다 트릭"의 사용을 용이하게 할 수 있다. 이것의 더욱 상세한 내용에 관해서는, 여기서 참고로 포함된 상술한 US 특허 US 5,671,236 및 US 5,854,810의 "람다 트릭"을 참조한다.

도 16을 이용하여, 람다 트릭의 용도를 설명할 수 있다. 오류 제어 코드 C'는, 서브코드로서 스크램블링 코드 C를 갖는다고 생각된다, 즉, C의 각 워드는, C'로부터의 워드이다. 코드 C'는 m=｜C'｜/｜C｜세트로 분할되고, 즉 A₁,A₂,...,A_m을 말하고, 각각 ｜C｜워드를 포함한다(여기서, ｜A｜는 세트 A의 요소의 수를 나타낸다). 도 16에서, 각 상기 세트는 ｜C｜행의 블록으로서 도시되어 있다. 인코딩될 수 있는 메시지의 수는 m이다. 메시지마다, 인코더는 그 메시지를 A_j로부터의 워드로 인코딩하는 지수 j가 있고, 즉 그 메시지는 그것의 인코딩된 버전이 존재하는 블록에 의해 결정된다. 인코더는, 목적 함수를 최적화하기 위해서 A_j에서 어느 코드어를 선택할 것인가를 선택한다.

일부의 당업자에게 있어서 동일한 원리는 C가 C'의 서브코드의 임의의 잉여류인 경우 적용한다는 것이 분명하다.

먼저, 디코더는 수신된 워드를 C'로부터의 코드어 c로 디코딩한다. 그 후, 디코더는, c가 A_j에 있는 지수 j를 찾는다. "역맵핑" 단계에서는, 전송된 메시지를 j로부터 검색한다.

바람직한 실시예에서, 각 A_j는 C의 잉여류이다. 즉, j마다, A_j로부터의 각 워드가 일부의 스크램블링 워드 c로부터 형태 c_j+c를 갖고, 즉, A_j={c_j+c｜c∈C}인 코드어 c_j가 존재한다. 이러한 바람직한 실시예에 의해 인코더가 (상술한 것처럼) 주어진 메시지에 대응한 잉여류를 효율적으로 결정할 수 있다. 또한, 디코더가 간단한 방식으로 코드어를 상기 인코딩된 메시지로 역맵핑할 수 있다.

상술한 것처럼, C'가 서브코드를 갖는 것을 제안한다. 이러한 바람직한 실시예에서는, C를 위한 반복 코드를 선택한다. 그러나, 각 리드-솔로몬 코드 C'는 반복코드를 포함하지 않는다. (상술한 것처럼) 종래의 리드-솔로몬 코드의 소수의 변경은, 리드-솔로몬 코드(동일한 오류 정정 능력, 가상으로 동일한 인코딩 및 디코딩 동작)의 모든 장점을 즐기지만 반복 코드를 사용하는 코드 C"가 생긴다.

결론을 내리면, 상기 제안된 본 발명은, (시간 및/또는 공간에서) 주어진 점의 저장 또는 전송 채널의 비트 오류 확률이 주어진 점의 이웃에서의 채널 입력과 그 점 자체에서의 채널 입력과의 함수로서 표현될 수 있다고 가정한다. 또한, 주어진 스트림에서 모든 채널 출력에 대한 상기 예상된 비트 오류율이 그 스트림에 대 한 주어진 함수의 평균으로서 표현될 수 있다고 가정한다. 상기 제안된 스크램블링 방법은, 작은 스크램블링 코드 C로부터 적절하게 선택된 스크램블링 코드어의 모듈로 q(이진수:q=2)가산을 포함하고, 이 방법은 유도 스크램블링이라고 한다. 이미 설명한 것처럼, (예측된) 비트 오류율(심볼의 예상 비트 오류 확률의 평균) 대신에, 본 발명은 마찬가지로 국부적 함수의 평균으로서 표현되거나 근사화될 수 있는 다른 함수에도 적용될 수 있고, 여기서, 이들 국부적 함수는, 주어진 격자 위치의 이웃 위치에만 의존한다. 이러한 대안의 성능 지수의 예시로는, 간단한 선형 필터링 연산 후 거듭제곱(즉, 제곱값)이고, 즉 필터의 출력 거듭제곱이다.

본 발명에서는, 스크램블링 코드 C에 관한 충분한 조건을 제공하여, 상기 메시지에 가산된 c^*에 의해, 상기 예상된 비트 오류율이 결코 균일하게 랜덤한 입력에 대해 그 예상값을 초과하지 않도록 스크램블링 코드어 c^*가 항상 존재한다.

상기 제안된 채널 데이터 스트림의 타일링을 사용하면, 스크램블링 코드 C는, 소수의 코드어만을 검색되게 하는, 2차원 광학 저장시에 사용된 것과 같은 상기 2차원 채널용 조건을 만족시키도록 구성될 수 있다. 다수의 방식은, 상기 제안된 유도 스크램블링 방법과 오류 정정 코드를 조합하도록 나타내어진다. 그 나타내어질 가능성이 없으면, 람다 트릭의 용도는 바람직한 근접법이다.

또한, 본 발명에 따른 인코딩 방법의 용도는, 기록매체에 기록되거나 전송선을 통해 신호로서 전송된 채널 데이터 스트림의 출력신호로부터 검출 가능하다. 통상의 기록매체에 대해, 채널 데이터 스트림의 제 1 심볼이 인코더의 출력과 일치할 가능성이 있지만, 작다. 실제로, 스트림은, 코드어를 각각 포함한 수천 또는 수백만의 연속적인 블록으로 이루어진다. 예를 들면, 이들 블록의 99%의 분수(결코 기록매체의 채널 오류로 인해 100%는 아님) 또는 그 이상에 대해, 기록매체에서 검색된(또는, 일반적으로, C로부터 가능한 모든 스크램블링 코드어 중에서, c_opt의 선택) 코드어의 제 1 심볼의 값이 본 발명에 따른 인코더에 의해 생성된 잡음 없는 코드어의 제 1 심볼과 일치할 확률은 사라졌다, 즉 일치될 수 없는데, 그 이유는 블록의 수가 아주 크기 때문이고, 이는 임의의 기록 응용에서 일반적으로 발견된다. 전형적인 블록 길이(즉, 코드어 길이)는 대략의 크기 "수천 바이트"이다. 전형적인 기록 매체는, 기가바이트 이상을 포함한다. 요약하면, 본 발명과 관련 없는 기록매체에 대해, 본 발명에서의 인코더를 이해하는 것이 가능하지 않아, 인코더에 기록매체에 저장된 사용자 데이터 스트림이 공급되는 경우, 스크램블링 코드어에 대한 대응한 선택은 기회를 지나칠 가능성을 갖는 기록매체 상에서 검출될 수 있는 스크램블링 코드어의 선택과 일치한다.

그래서, 본 발명에 따른 인코딩 방법의 사용법을 검출하기 위해서, 다음의 단계:

(1) 인코딩된 데이터 스트림(디스크 당 수천 블록)을 검색하는 단계와,

(2) 본 발명에 따른 방법에 따라 데이터 스트림을 재인코딩하는 단계를 적용할 수 있다.

이 재인코딩된 데이터 스트림들이 디스크에 기록된 것과 같은 스트림과 "종종" 일치하는 경우, 본 발명에 따른 인코딩 방법을 사용하는 가능성은 거의 1이다.

그것은 본 발명의 또 다른 실시예의 목록을 수반한다. 이들 실시예에서는, 확장부가 존재하지 않는 점에 대해 하찮게 다루어지고, 스크램블링 코드어가 사용된 선택은, 별도의 수단으로 수신기에게 전송되어야 한다.

사용자 데이터 심볼 스트림(m)을 스크램블링 코드어 심볼 스트림(c)의 세트 C를 사용하여 채널 심볼 데이터 스트림(b)으로 인코딩하기 위한 인코딩 장치의 실시예에서, 심볼 스트림은 I의 부분집합 J의 집합 X와 즉 스트림 당(전체) 성능 지수 함수(G)를 사용하여, 심볼 입력 위치 I의 세트에 관해 정의된 심볼 값의 정렬된(ordered) 세트이고,

- 적어도 하나의 코드어는 적어도 2개의 서로 다른 심볼 값을 갖고,

- 상기 부분집합 J는 C의 균형 잡힌 부분집합이고,

- 상기 스트림 당 성능 지수 함수(G)는, (X로부터) 모든 부분집합 J에 관해 값이 구해진 심볼 값에 대해서 국부적 성능 지수 함수(테이블)g의 값의 선형 조합이고,

상기 인코딩 장치는,

- 코드어(c')를 상기 사용자 데이터 심볼 스트림(m) 상에 맵핑한 결과의 스트림 당 성능 지수 함수(G)의 값(v)을 결정하는 처리부와,

- 상기 코드어(c')의 상기 사용자 데이터 스트림(m') 상의 맵핑의 상기 스트림 당 메리트 값(v)으로부터 최적의 스트림 당 메리트 값(v_opt)을 선택하고 상기 최적의 메리트 값(v_opt)을 사용하여 대응한 최적의 스크램블링 코드어(c_opt)를 선택하는 선택부와,

- (잡음) 채널(L)에 대해 입력 심볼 스트림(b)으로서의 역할을 하도록, 최적의 코드어(c_opt)를 사용자 데이터 스트림(m) 상에 맵핑하는 것으로 생기는 맵핑된 사용자 데이터 스트림(m'_opt)을 얻는 맵핑부(스크램블링부로도 알려짐)를 구비한다.

이러한 실시예는,

- 입력 위치(I)의 세트가 격자 구조를 갖고,

- 상기 집합(X)이 모든 입력 위치(I에 관해서 i)의 세트(의 부분집합)의 인접 위치(i-N)의 정렬된 세트로 이루어진 집합이고,

- 상기 코드(C)는 선형 코드의 잉여류이고,

- 상기 코드(C)의 크기는 적어도 4이다는 점에서, 더욱 향상될 수 있다.

또 다른 실시예는, 스크램블링 코드(C)가 적어도 1차원으로 순환적이다는 점에서 향상된다.

인코딩 장치는, 스크램블링 코드(C)가 특정 크기를 갖는 반복 코드(k)이고,

- 상기 지수 세트(I)가 부분집합(I_u)의 수(U)로 분할되고, 이때 그 코드(k)의 크기는, 최대 부분집합의 수(U)와 같고,

- 상기 집합(X)에 있는 모든 부분집합(J)에 대해, 세트(J)에 있는 서로 다른 지수(i) 모두가 I의 별개의 부분집합(I_u')에 포함된다는 점에서 더욱 향상된다.

비어 있지 않은 코드(C)용 지수 세트(I)로부터 특정 크기(j)를 갖는 입력 위치(J)의 균형 잡힌 부분집합은, 스크램블링 코드(C)로부터의 스크램블링 코드어(c)를 지수의 부분집합(J)에 대해 제한하는 것이 동등하게 여러번 일어나고, 가능한 모든 시퀀스의 길이(j)가 균형 잡힌 부분집합(J)의 크기와 같은 경우의 인코딩 장치에서 사용될 수 있다.

상기 인코딩 장치는, 부분집합(i-N)에 관한 심볼값의 정렬된 부분집합(y)의 국부적 성능 지수 함수(g)가 상술한 채널 입력 심볼의 정렬된 부분집합(y)에 의해 지수(i)에서 채널 입력에 대한 채널(L)로 나타내어진 예상 정보 양(P)의 함수이고, 상기 최적의 메리트 값(v_opt)이 최대 메리트 값이다는 점에서 더욱 개량될 수 있다.

또 다른 개선점은, 상기 채널로 나타내어진 상기 예상 정보 양(P)이 지수(i)에서의 상기 예측된 심볼 오류율인 것이다.

또 다른 개선점은, 상기 국부적 성능 지수 함수(g)가 이웃(i-N)에 필터 입력 심볼로 이루어진 정렬된 부분집합을 제공한 출력 지수(i)에서의 필터의 출력 전력이다는 점에서 달성될 수 있다.

상기 인코더를 개선하기 위해서는, 부분집합(i-N)에 관해 상기 채널 입력 심볼의 정렬된 부분집합(y)에 의해 지수(i)에서의 채널 입력에 대한 채널(L)로 나타내어진 상기 예상된 정보 양(P)은, 부분집합(i-N)에 없는 지수(i')에서의 심볼의 값에서 최소화된다.

상기 인코더를 개선하기 위해서는, 코드어(c')를 상기 사용자 데이터 심볼 스트림(m)에 맵핑한 결과의 스트림 당 성능 지수 함수(G)의 값(v)을 결정하는 처리부는, 히스토그램으로 이루어진 세트를 사용한다.

상기 인코더를 개선하기 위해서는, 스크램블링 코드(C)는, 사용자 데이터 심 볼 스트림(m)이 인코딩되는 오류 제어코드(C')의 서브코드이다.

Claims (17)

1. 사용자 데이터 스트림(m)을 채널 데이터 스트림(y)으로 인코딩하는 인코딩 장치로서,

   상기 사용자 데이터 스트림(m)을 상기 사용자 데이터 스트림(m)보다 적어도 하나 더 많은 심볼을 포함하는 중간 데이터 스트림(i)으로 변환하는 확장부(150)와,

   스크램블링 코드(C)로부터 스크램블링 스트림(c)마다 상기 중간 데이터 스트림(i)을 사용하여 그 스크램블링 스트림(c)에 대한 성능 지수의 값(v)을 반복적으로 결정하는 처리부(100,200,500,600)를 구비하고, 상기 스크램블링 스트림(c)이 상기 중간 데이터 스트림(i)처럼 동등하게 많은 수의 심볼을 포함하고, 상기 성능 지수는 상기 스크램블링 스트림(c)의 부분의 집합에 걸친 합이고, 이 부분은 상기 스크램블링 스트림으로부터 적어도 2개의 심볼 위치를 포함하고, 상기 합의 각 항은 상기 중간 스트림(i)의 대응한 부분을 사용하여 스크램블링 스트림(c)의 상기 부분에 대한 성능 지수이고, 상기 스크램블링 스트림(c)의 상기 부분 각각에서 각기 가능한 심볼의 조합은 상기 스크램블링 코드(C)로부터 동등하게 많은 스크램블링 스트림(c)에서 일어나고,

   상기 성능 지수 값(v)으로부터 최적 메리트 값(v_opt)을 선택하고 상기 성능 지수가 상기 최적의 메리트 값(v_opt)과 같은 최적의 스크램블링 스트림(c_opt)을 선택하는 선택부(300)를 더 구비하고,

   채널에 출력하기 위해 상기 채널 데이터 스트림(y)을 얻도록 상기 최적의 스크램블링 스트림(c_opt)의 심볼을 상기 중간 데이터 스트림(i)의 대응한 심볼 상에 맵핑하는 적어도 하나의 맵핑부(400)를 또 더 구비한 것을 특징으로 하는 인코딩 장치.
2. 제 1 항에 있어서,

   상기 적어도 하나의 맵핑부(400)는, 스크램블링 스트림(c)의 심볼을 상기 중간 데이터 스트림(i)의 대응한 심볼 상에 맵핑하도록 작동하고, 상기 처리부는, 상기 스크램블링 스트림(c)의 심볼을 상기 중간 데이터 스트림(i)의 대응한 심볼 상에 맵핑하는 것으로부터의 결과를 사용하여서 상기 성능 지수의 메리트 값(v)을 스크램블링 스트림(c)마다 결정하도록 작동하는 것을 특징으로 하는 인코딩 장치.
3. 제 1 항에 있어서,

   상기 적어도 하나의 맵핑부(400)는, 상기 스크램블링 스트림(c)의 상기 심볼을 상기 중간 데이터 스트림(i)의 대응한 심볼에 가산하여서 스크램블링 스트림(c)의 심볼을 상기 중간 데이터 스트림(i)의 대응한 심볼 상에 맵핑하는 수단을 구비한 것을 특징으로 하는 인코딩 장치.
4. 제 1 항에 있어서,

   상기 스크램블링 코드(C)는 반복코드인 것을 특징으로 하는 인코딩 장치.
5. 제 4 항에 있어서,

   상기 처리수단(600)은, 적어도 2개의 히스토그램(H)으로부터 채널 데이터 스트림의 부분에 대한 메리트 값의 합을 결정하도록 작동하고, 상기 각 히스토그램은, 심볼의 조합 발생 빈도를 상기 중간 데이터 스트림(i)의 다수의 상기 부분에 저장하는 것을 특징으로 하는 인코딩 장치.
6. 제 1 항에 있어서,

   상기 채널 데이터 스트림은 1차원 데이터 스트림이고, 상기 부분 각각은, 특히 3 내지 8비트의 범위 내에서 고정된 수의 연속 심볼을 포함한 것을 특징으로 하는 인코딩 장치.
7. 제 1 항에 있어서,

   상기 채널 데이터 스트림은 2차원 데이터 스트림이고, 상기 채널 데이터는, 2차원 격자의 무한대 범위의 스트립을 따라서의 제 1 방향과, 유한대 범위의 스트립을 따라서의 상기 제 1 방향과 실질적으로 직교하는 제 2 방향으로 전개하고, 상기 스트립은 상기 제 2 방향을 따라 서로의 위에 적층된 다수의 심볼 행으로 이루어지고, 상기 부분 각각은 고정된 수의 심볼을 포함한 것을 특징으로 하는 인코딩 장치.
8. 제 7 항에 있어서,

   상기 심볼은, 유사 정사각형 격자, 유사 직사각형 또는 6각형 격자의 격자점에 배치된 것을 특징으로 하는 인코딩 장치.
9. 제 8 항에 있어서,

   상기 부분 각각은 6각형 격자의 격자점에 배치된 7개의 심볼을 구비하고, 각 사용자 부분은 중심 사용자 심볼과 6개의 최근접 인접 심볼로 이루어진 것을 특징으로 하는 인코딩 장치.
10. 제 1 항에 있어서,

    상기 확장부는, 상기 사용자 데이터 스트림(m)을, 적어도 하나의 심볼을 상 기 사용자 데이터 스트림(m)에 부가하여서 상기 중간 데이터 스트림(i)으로 변환하도록 동작하고, 상기 적어도 하나의 심볼의 값은 상기 인코더와 디코더에 알려지고, 가능한 모든 사용자 데이터 스트림에도 동일하게 알려진 것을 특징으로 하는 인코딩 장치.
11. 제 1 항에 있어서,

    상기 확장부는, 상기 사용자 데이터 스트림(m)을 오류정정코드(C')로부터의 워드인 중간 스트림(i)으로 변환하도록 동작하고, 스크램블링 코드(C)는 상기 오류정정코드(C')의 서브코드의 잉여류이고, 상기 스크램블링 코드(C)로부터의 스크램블링 스트림(c)을 상기 중간 스트림(i) 상에 맵핑한 결과는 상기 오류정정코드(C')로부터의 워드인 것을 특징으로 하는 인코딩 장치.
12. 사용자 데이터 스트림(m)을 채널 데이터 스트림(y)으로 인코딩하는 인코딩 방법으로서,

    상기 사용자 데이터 스트림(m)을 상기 사용자 데이터 스트림(m)보다 적어도 하나 더 많은 심볼을 포함하는 중간 데이터 스트림(i)으로 변환하는 단계와,

    스크램블링 코드(C)로부터 스크램블링 스트림(c)마다 상기 중간 데이터 스트림(i)을 사용하여 그 스크램블링 스트림(c)에 대한 성능 지수의 값(v)을 반복적으 로 결정하는 단계를 포함하고, 상기 스크램블링 스트림(c)이 상기 중간 데이터 스트림(i)처럼 동등하게 많은 수의 심볼을 포함하고, 상기 성능 지수는 상기 스크램블링 스트림(c)의 부분의 집합에 걸친 합이고, 이 부분은 상기 스크램블링 스트림으로부터 적어도 2개의 심볼 위치를 포함하고, 상기 합의 각 항은 상기 중간 스트림(i)의 대응한 부분을 사용하여 스크램블링 스트림(c)의 상기 부분에 대한 성능 지수이고, 상기 스크램블링 스트림(c)의 상기 부분 각각에서 각기 가능한 심볼의 조합은 상기 스크램블링 코드(C)로부터 동등하게 많은 스크램블링 스트림(c)에서 일어나고,

    상기 성능 지수 값(v)으로부터 최적 메리트 값(v_opt)을 선택하고 상기 성능 지수가 상기 최적의 메리트 값(v_opt)과 같은 최적의 스크램블링 스트림(c_opt)을 선택하는 단계를 더 포함하고,

    채널에 출력하기 위해 상기 채널 데이터 스트림(y)을 얻도록 상기 최적의 스크램블링 스트림(c_opt)의 심볼을 상기 중간 데이터 스트림(i)의 대응한 심볼 상에 맵핑하는 단계를 또 더 포함한 것을 특징으로 하는 인코딩 방법.
13. 채널 데이터 스트림(r)을, 청구항 11의 방법에 따라 인코딩된 사용자 데이터 스트림(m)으로 디코딩하는 디코딩 장치로서,

    상기 채널 데이터 스트림(r)을 상기 오류정정코드(C')의 채널 코드어(y)로 디코딩하는 ECC 디코딩부(700)와,

    스크램블링 코드어(c)를 중간 데이터 스트림(i)에 맵핑하는 것이 상기 채널 코드어(y)에서 생기도록 상기 채널 코드어(y)로부터 중간 데이터 스트림(i)과 스크램블링 코드어(c)를 찾는 분리부(800)와,

    사용자 데이터 스트림(m)을 사용자 데이터 스트림(m)보다 적어도 하나 더 많은 심볼을 포함하는 중간 데이터 스트림으로 확장하는 것이 상기 중간 데이터 스트림(i)에서 생기도록 상기 중간 데이터 스트림(i)으로부터 사용자 데이터 스트림(m)을 검색하는 역맵핑부(900)를 구비한 것을 특징으로 하는 디코딩 장치.
14. 채널 데이터 스트림(r)을, 청구항 11의 방법에 따라 인코딩된 사용자 데이터 스트림(m)으로 디코딩하는 디코딩 방법으로서,

    상기 채널 데이터 스트림(r)을 상기 오류정정코드(C')의 채널 코드어(y)로 디코딩하는 단계와,

    스크램블링 코드어(c)를 중간 데이터 스트림(i)에 맵핑하는 것이 상기 채널 코드어(y)에서 생기도록 상기 채널 코드어(y)로부터 중간 데이터 스트림(i)과 스크램블링 코드어(c)를 찾는 단계와,

    사용자 데이터 스트림(m)을 사용자 데이터 스트림(m)보다 적어도 하나 더 많은 심볼을 포함하는 중간 데이터 스트림으로 확장하는 것이 상기 중간 데이터 스트림(i)에서 생기도록 상기 중간 데이터 스트림(i)으로부터 사용자 데이터 스트림(m)을 검색하는 단계를 포함한 것을 특징으로 하는 디코딩 방법.
15. 채널 데이터 스트림(r)을 청구항 1에 기재된 인코딩 방법에 따라 인코딩된 사용자 데이터 스트림(m)으로 저장한 기록매체.
16. 채널 데이터 스트림(r)을 청구항 1에 기재된 인코딩 방법에 따라 인코딩된 사용자 데이터 스트림(m)으로 갖는 신호.
17. 컴퓨터 상에서 컴퓨터 프로그램이 동작하는 경우 컴퓨터가 청구항 12 또는 14에 기재된 방법의 단계를 수행하도록 하는 프로그램 코드 수단을 구비한 컴퓨터 프로그램.

Images