KR101143282B1

KR101143282B1 - 연쇄 반응 코드의 체계적 인코딩 및 디코딩

Info

Publication number: KR101143282B1
Application number: KR1020057005861A
Authority: KR
Inventors: 엠. 아민 쇼크롤라히; 마이클 지. 루비
Original assignee: 디지털 파운튼, 인크.
Priority date: 2002-10-05
Filing date: 2003-10-01
Publication date: 2012-05-08
Anticipated expiration: 2023-10-01
Also published as: EP2348640B1; CN100539439C; US20040075593A1; JP5675876B2; US20090189792A1; US6909383B2; AU2003277198A8; JP4546246B2; AU2003277198A1; US7532132B2; USRE43741E1; EP2357731B1; US20050242974A1; WO2004034589A3; US20080180285A1; EP2357731A1; WO2004034589A2; WO2004034589A9; US9236885B2; EP1552617A2

Abstract

데이터를 연쇄 반응 코드로 인코딩하는 방법은, 입력 데이터로부터 한 세트의 입력 심볼들을 생성하는 단계를 포함한다. 다음으로는, 한 세트의 입력 심볼들로부터, 각각이 비-체계적 출력 심볼들의 알파벳으로부터 선택되며 하나 이상의 입력 심볼들의 함수로서 생성되는, 하나 이상의 비-체계적 출력 심볼들이 생성된다. 이러한 인코딩 프로세스의 결과로서, (ⅰ) 사전설정된 갯수의 비-체계적 출력 심볼들 또는 (a) 복구될 입력 심볼들의 서브세트에 포함되지 않은 입력 심볼들과 (b) 하나 이상의 비-체계적 출력 심볼들의 (ⅱ) 조합으로부터, 입력 심볼들의 세트에 대한 임의의 서브세트가 복구될 수 있다.

연쇄 반응 코드, 입력 심볼, 비-체계적 출력 심볼, 인코딩, 디코딩, 키 생성기

Description

연쇄 반응 코드의 체계적 인코딩 및 디코딩 {SYSTEMATIC ENCODING AND DECODING OF CHAIN REACTION CODES}

관련 출원들에 대한 상호-참조

본 출원은, 그 내용 전부를 여기에서 참조하고 있는, "Systematic Encoding and Decoding of Chain Reaction Codes"라는 명칭으로 2002년 10월 5일에 출원된 미국 가명세출원 제 60/319,597호의 우선권을 주장한다.

배경

다음의 본 발명은 모든 유형의 데이터를 인코딩 및 디코딩하는 시스템들 및 방법들에 관한 것으로서, 보다 구체적으로는, 연쇄 반응 코드들을 사용해 데이터를 인코딩 및 디코딩하는 시스템들 및 방법들에 관한 것이다.

통신 채널을 통한 송신자와 수신자간의 데이터 전송은 많은 논문의 주제가 되어 왔다. 바람직하게도, 반드시 그런 것은 아니지만, 수신자는 채널을 통해 송신자에 의해 전송된 데이터의 정확한 복사본을 일정 수준의 확실성으로 수신하기를 원한다. (물리적으로 실현 가능한 대부분의 시스템들에 해당되듯이) 채널이 완벽한 충실도(perfect fidelity)를 갖지 않을 경우, 관심사는 전송 중에 손실 또는 왜곡된 데이터를 다루는 방법이다. 대개는 손실된 데이터(소실들)가 손상된 데이터(오류들)보다 다루기가 더 용이한데, 그 이유는, 언제 손상된 데이터가 잘못 수신된 데이터인지를 수신자가 항상 식별할 수 있는 것은 아니기 때문이다. 소실들 및/또 는 오류들에 대한 정정을 위해, 많은 오류-정정 코드들이 개발되어 왔다. 통상적으로, 그를 통해 데이터가 전송되고 있는 채널의 불충실도 및 전송 중인 데이터의 특징에 관한 소정 정보에 기초해, 사용되는 특정 코드가 선택된다. 예를 들어, 채널이 불충실도의 긴 주기들을 갖는 것으로 공지된 경우라면, 그러한 애플리케이션에는 버스트 오류 코드(burst error code)가 가장 적합할 수 있다. 단시간의 아주 드문 오류들만이 예상되는 경우라면, 간단한 패리티 코드가 최선일 수 있다.

코드 선택의 또 한가지 고려 사항은 전송에 사용되는 프로토콜이다. 인터넷의 경우, 패킷 프로토콜이 데이터 전송에 사용된다. 그러한 프로토콜을 인터넷 프로토콜 또는 간단히 "IP"라고 한다. 파일 또는 다른 데이터 블록이 IP 네트워크를 통해 전송되어야 할 경우, 파일 또는 다른 데이터 블록은 균등한 크기의 입력 심볼들로 분할되고 입력 심볼들은 일련의 패킷들로 배치된다. 입력 심볼이 실제 비트 스트림으로 분해되는지의 여부에 관계없이, 입력 심볼의 "크기"는 비트로 측정될 수 있는데, 입력 심볼이 2^M개 심볼들의 알파벳으로부터 선택될 경우, 입력 심볼은 M 비트의 크기를 가진다. 이러한 패킷-기반 통신 시스템에서는, 패킷 지향형 코딩 방식(packet oriented coding scheme)이 적합할 수 있다.

네트워크에서의 소실들에도 불구하고 의도된 수신자가 원래 파일의 정확한 복사본을 복구할 수 있다면, 전송을 신뢰할 수 있다고 한다. 인터넷의 경우, 패킷 소실은 종종, 돌발적인 정체로 인해 라우터의 버퍼링 메커니즘이 용량 한도에 도달하여 입력 중인 패킷들을 누락하게 되기 때문에, 발생한다. 전송 동안의 소실들을 방지하는 것이 많은 연구의 주제가 되어 왔다.

TCP(Transport Control Protocol)는 접수확인 응답(acknowledgement) 메커니즘을 가진, 흔히 사용되는 점-대-점 패킷 제어 방식이다. TCP를 사용해, 송신자는 순서화된 패킷들을 송신하고 수신자는 각 패킷의 수신을 접수확인 응답한다. 패킷이 손실되면, 송신자에게로 접수확인 응답이 송신되지 않을 것이고 송신자는 패킷을 재송신할 것이다. TCP와 같은 프로토콜들의 경우, 접수확인 응답 패러다임으로 인해, 상실된 패킷들은, 접수확인 응답의 부재에 응답하거나 수신자로부터의 명시적인 요청에 응답하여, 재전송될 수 있으므로, 전체적인 실패없이, 패킷들이 상실될 수 있다.

접수확인 응답-기반 프로토콜들이 많은 애플리케이션들에 대체로 적합하고 현재 인터넷을 통해 실제로 널리 사용되고 있기는 하지만, Luby I에서 설명된 바와 같은 소정 애플리케이션들에 대해서는 접수확인 응답-기반 프로토콜들이 불충분하며, 가끔은 완전히 실행 불가능할 수도 있다.

전송 문제를 해결하기 위해 제안되어 온 한가지 해결책은 접수확인 응답-기반 프로토콜을 사용하지 않는 대신, 신뢰성을 증대시키기 위해, 리드-솔로몬 코드들(Reed-Solomon codes), Tornado 코드들, 또는 연쇄 반응 코드들과 같은, FEC(Forward Error-Correction) 코드들을 사용하는 것이다. 기본적인 아이디어는, 컨텐츠를 구성하는 입력 심볼들만을 송신하는 대신에 컨텐츠로부터 생성된 출력 심볼들을 송신하는 것이다. 리드-솔로몬 또는 Tornado 코드들과 같은, 통상적인 소실 정정 코드들(erasure correcting codes)은 고정 길이 컨텐츠에 대해 고정 갯수 의 출력 심볼들을 생성한다. 예를 들어, K개 입력 심볼들에 대해, N개의 출력 심볼들이 생성될 수 있다. 이러한 N개의 출력 심볼들은 원래의 K개 입력 심볼들 및 (N-K)개의 잉여 심볼들을 구비할 수 있다. 저장 장치가 허용한다면, 서버는 각각의 컨텐츠에 대해 한번씩만 출력 심볼들의 세트를 계산하고 캐루젤 프로토콜(carousel protocol)을 사용해 출력 심볼들을 전송할 수 있다.

일부 FEC 코드들에서의 한가지 문제점은, 이들이 연산을 위해 과도한 계산력 또는 메모리를 요한다는 점이다. 또 하나의 문제점은, 출력 심볼들의 수가 코딩 프로세스 이전에 판정되어야 한다는 점이다. 이로 인해, 패킷들의 손실율이 과도 평가된다면 비효율들이 초래될 수 있고, 패킷들의 손실율이 과소 평가된다면 실패할 수 있다.

통상적인 FEC 코드들의 경우, 생성될 수 있는 가능한 출력 심볼들의 수는 컨텐츠가 분할되는 입력 심볼들의 수와 동일한 차수(same order of magnitude)이다. 통상적으로, 반드시 그런 것은 아니지만, 이러한 입력 심볼들의 대다수는 송신 단계 이전의 선행 처리 단계에서 생성된다. 이러한 출력 심볼들은, 원래의 컨텐츠와 길이가 동일하거나 원래의 컨텐츠보다 길이가 약간 더 긴, 출력 심볼들의 임의의 서브세트로부터 모든 입력 심볼들이 재생될 수 있다는 특성을 가진다.

"Information Additive Code Generator and Decoder for Communication Systems"(이하 "Luby I")이라는 명칭의 미국 특허 제 6,307,487호 및 "Multi-Stage Code Generator and Decoder for Communication Systems"(이하 "Raptor")라는 명칭의 미국 특허출원 제 10/032,156호에 설명되어 있는 "연쇄 반응 코딩"은 상기 쟁점 들에 역점을 두어 다루는 순방향 오류 정정의 상이한 형태를 표현한다. 연쇄 반응 코드들의 경우, 생성될 수 있는 가능한 출력 심볼들의 풀이 입력 심볼들의 수보다 더 큰 차수이고, 가능성이 높은 풀로부터 랜덤 출력 심볼이 아주 빠르게 생성될 수 있다. 연쇄 반응 코드들의 경우, 출력 심볼들은 송신 단계와 동시에, 필요에 따라, 지체없이 생성될 수 있다. 연쇄 반응 코드들은, 원래 컨텐츠보다 길이가 약간 더 긴, 무작위로 생성된 출력 심볼들 세트의 임의의 서브세트로부터, 컨텐츠의 모든 입력 심볼들이 재생될 수 있다는 특성을 가진다.

"On Demand Encoding With a Window"라는 명칭으로 2000년 9월 22일에 출원된 미국 특허출원 제 09/668,452호 및 "Generating High Weight Output symbols Using a Basis"라는 명칭으로 2000년 10월 18일에 출원된 미국 특허출원 제 09/691,735호와 같은 문서들에서, 다양한 연쇄 반응 코딩 시스템들에 대한 다른 설명들을 찾아볼 수 있다.

연쇄 반응 코딩 시스템의 일부 실시예들은 인코더 및 디코더로 이루어진다. 데이터는 블록 또는 스트림의 형태로 인코더에 제시될 수 있고, 인코더는 블록 또는 스트림으로부터 지체없이 출력 심볼들을 생성할 수 있다. 일부 실시예들, 예를 들어, Raptor에서 설명된 실시예들에서는, 데이터가 정적 인코더를 사용해 오프라인으로 사전-인코딩될 수 있고, 복수개의 원래 데이터 심볼들 및 정적 출력 심볼들로부터 출력 심볼들이 생성될 수 있다.

연쇄 반응 코딩 시스템의 일부 실시예들에서, 인코딩 및 디코딩 프로세스는 가중치 도표(weight table)에 의존한다. 가중치 도표는 소스 심볼들의 세트에 대 한 확률 분포를 설명한다. 즉, 1과 소스 심볼들 수 사이의 임의의 숫자(W)에 대해, 가중치 도표는 고유한 확률(P(W))을 지시한다. 실질적으로 W의 많은 값들에 대해 P(W)가 0일 수 있는데, 그런 경우라면, P(W)가 0이 아닌 가중치들(W)만을 포함하는 것이 바람직할 수도 있다.

연쇄 반응 코딩 시스템의 일부 실시예들에서는, 모든 출력 심볼에 대해 키가 무작위로 생성되는 방식으로, 출력 심볼들이 생성된다. 키에 기초해, 가중치 도표로부터 가중치(W)가 계산된다. 그 다음, W 소스 심볼들의 랜덤 서브세트가 선택된다. 그 다음, 이러한 소스 심볼들의 XOR가 출력 심볼일 것이다. 이하에서는, 이러한 소스 심볼들을 출력 심볼의 이웃들 또는 동료들(neighbors and associates)이라고 한다. 이러한 기본 방식에 대한 다양한 변경들 및 확장들이 가능하며 상술된 특허들 및 특허출원들에서 논의되어 왔다.

출력 심볼이 생성되고 나면, 출력 심볼은 출력 심볼의 키 또는 키가 생성될 수 있는 방법에 대한 지시와 함께 의도된 수신자들에게로 송신될 수 있다. 일부 실시예들에서, 많은 출력 심볼들은, 예를 들어, "Scheduling of multiple files for serving on a server"라는 명칭으로 2001년 2월 22일에 출원된 미국 특허출원 제 09/792,364호에 설명되어 있는 바와 같이, 하나의 전송 패킷을 구성할 수 있다.

소정 애플리케이션들에서는, 소스 심볼들을 먼저 전송한 다음 출력 심볼들을 송신하는 것으로써, 전송을 계속하는 것이 바람직할 수 있다. 이러한 코딩 시스템을 여기에서는 체계적 코딩 시스템이라고 한다. 수신측에서, 수신기는 최대한 많은 원래의 입력 심볼들을 수신하고자 하며, 수신되지 않은 입력 심볼들을 하나 이 상의 출력 심볼들로 대체하고, 대체된 출력 심볼들을 사용해 누락된 입력 심볼들을 복구하고자 할 수 있다. 출력 심볼들의 전송은, 수신기의 명시적인 요청없이, 예방적으로 수행되거나, 반응적으로, 즉, 수신기의 명시적인 요청에 응답하여 수행될 수 있다. 예를 들어, 무손실 또는 극소량의 손실이 예상되는 애플리케이션들의 경우, 원래의 입력 심볼들을 먼저 송신하고 소실들이 있는 경우에만 추가적인 출력 심볼들을 송신하는 것이 유리할 수 있다. 이런 식으로, 손실들이 없다면, 디코딩은 수행될 필요가 없다. 또 하나의 애플리케이션으로서, 하나 이상의 수신자들에게 라이브 비디오 스트림을 전송하는 경우를 생각한다. 약간의 손실이 예상될 경우, 연쇄 반응 코딩을 사용해 데이터를 보호하는 것이 바람직할 수 있다. 라이브 전송의 특징 때문에, 수신기는 기껏해야 소정 시간 동안의 데이터의 특정 부분만을 버퍼링할 수 있다. 이 시간 이후에 수신된 심볼들의 수가 데이터의 완전 재구성을 위해 불충분하다면, 소정 애플리케이션들의 경우, 지금까지 수신된 데이터 부분들을 비디오 플레이어로 전달하는 것이 유리할 수 있다. 소정 애플리케이션들의 경우 및 적절한 소스 코딩 방법들이 사용되는 경우, 비디오 플레이어는 열화된 품질로 그 데이터를 재생할 수 있다. 일반적으로, 애플리케이션들이 부분적으로 복구된 데이터조차 이용할 수 없는 경우라면, 체계적 코딩 시스템을 사용하는 것이 유리할 수 있다.

체계적 코딩 시스템들을 발생시키기 위해, Luby I 또는 Raptor에서 설명된 바와 같은 연쇄 반응 코딩 시스템들의 실시예들을 직접적으로 변경하는 것은 일반적으로 비효율들을 초래한다. 예를 들어, 연쇄 반응 코딩 시스템에서 먼저 전송된 심볼들이 원래의 심볼들을 구비한다면, 원래 데이터를 복구하기 위해서는, 원래 심볼들과 동일한 차수의 다수의 순수 출력 심볼들을 수신해야 할 수 있다. 다시 말해, 원래 심볼들의 수신은 디코딩 프로세스를 최소 한도로 도울 수 있을 뿐이므로, 디코딩 프로세스는 전반적으로 수신된 나머지 심볼들에 의존해야 한다. 이로 인해, 불필요하게 높은 수신 오버헤드가 초래된다.

따라서, 필요한 것은, 효율적인 인코딩 및 디코딩 알고리즘들을 가지며 연쇄 반응 코딩 시스템과 유사한 수신 오버헤드를 갖는, 연쇄 반응 코딩 시스템의 체계적 버전이다.

발명의 요약

본 발명은 체계적 연쇄 반응 인코딩 및 디코딩 프로세스들을 사용해 데이터를 인코딩 및 디코딩하는 시스템들 및 방법들을 제공한다. 이러한 개시는 다수의 애플리케이션들에서 사용될 수 있는데, 그 중 하나가 적은 계산 비용으로 데이터가 좀더 빠르고 신뢰성 있게 통신되는 데이터 통신 시스템이다.

본 발명의 일 실시예에서는, 데이터를 연쇄 반응 코드로 인코딩하는 방법이 제시된다. 먼저, 데이터로부터 입력 심볼들의 세트가 생성된다. 다음으로는, 입력 심볼들의 세트로부터, 각각이 비-체계적 출력 심볼들의 알파벳으로부터 선택되며 하나 이상의 입력 심볼들의 함수로서 생성되는, 하나 이상의 비-체계적 출력 심볼들이 생성된다. 이러한 인코딩 프로세스의 결과로서, (ⅰ) 소정 갯수의 비-체계적 출력 심볼들 또는 (a) 복구될 입력 심볼들의 서브세트에 포함되지 않은 입력 심볼들과 (b) 하나 이상의 비-체계적 출력 심볼들의 (ⅱ) 조합으로부터, 입력 심볼들 의 세트에 대한 임의의 서브세트가 복구될 수 있다.

다음의 도면들 및 상세한 설명을 고려하면, 본 발명의 추가적인 실시예들 및 특징들을 더 잘 이해할 수 있다.

도면의 간단한 설명

도 1A 및 도 1B는 비-체계적 연쇄 반응 인코더 및 디코더의 실시예들을 각각 도시한다.

도 2는 연쇄 반응 디코딩 프로세스에서 사용되는 원래 입력 심볼들로부터의 출력 심볼 생성을 도시한다.

도 3은 연쇄 반응 디코딩 프로세스에 사용되는 예시적인 디코딩 그래프를 도시한다.

도 4는 도 3에 나타낸 디코딩 그래프에 대한 디코딩 행렬을 도시한다.

도 5는 연쇄 반응 디코딩 프로세스에 사용되는 변형된 디코딩 그래프를 획득하기 위한 예시적인 절차를 도시한다.

도 6은 연쇄 반응 디코딩 프로세스에서 사용되는 변형된 디코딩 방정식을 도시한다.

도 7A는, 본 발명에 따른, 체계적 연쇄 반응 코드들을 사용해 데이터를 인코딩하는 예시적인 방법을 도시한다.

도 7B는, 본 발명에 따른, 체계적 연쇄 반응 코드들을 디코딩하는 예시적인 방법을 도시한다.

도 7C는 본 발명의 일 실시예에 따른 체계적 코딩 및 디코딩을 이용하는 통 신 시스템의 블록도를 도시한다.

도 8A는 본 발명의 일 실시예에 따른 체계적 인코더의 연산을 도시한다.

도 8B는 본 발명의 일 실시예에 따른 체계적 디코더의 연산을 도시한다.

도 9A는 본 발명의 일 실시예에 따른 체계적 인코더의 일 실시예를 도시한다.

도 9B는 본 발명의 일 실시예에 따른 체계적 디코더의 일 실시예를 도시한다.

도 10은, 본 발명에 따른, 체계적 키들을 생성하기 위한 제 1 방법을 도시한다.

도 11은, 본 발명에 따른, 체계적 키들을 생성하기 위한 제 2 방법을 도시한다.

도 12은, 본 발명에 따른, 체계적 키들을 생성하기 위한 제 3 방법을 도시한다.

도 13은, 본 발명에 따른, 체계적 키들을 생성하기 위한 제 4 방법을 도시한다.

도 14는, 본 발명에 따른, 체계적 및 비-체계적 심볼들을 가진 연쇄 반응 코드를 디코딩하기 위한 방법을 도시한다.

도 15 내지 도 17은 본 발명에 대한 일 실시예에서의 인코딩 및 디코딩 프로세스들을 도시한다.

간략화 및 편의를 위해, 앞선 도면들에서 식별된 사양들 및 컴포넌트들은 후 속 도면들에서도 그들의 참조 번호들을 유지한다.

실시예들의 상세한 설명

Ⅰ. 비-체계적 연쇄 반응 인코더 & 디코더

도 1A 및 도 1B는, 각각, Luby I 및 Raptor에서 설명된 바와 같은, 비-체계적 연쇄 반응 인코더(130) 및 디코더(170)의 실시예들을 도시한다. Luby I 및 Raptor에서와 같이 언급되지는 않지만, 이러한 실시예들의 아키텍처 및 연산을, 후술되는 체계적 인코더들 및 디코더들과 구별하기 위해, 이러한 실시예들을 여기에서는 "비-체계적"이라고 한다.

이제 도 1A를 참조하면, 비-체계적 인코더(130)가 입력 심볼들(IS(0), IS(1), ...) 및 키 생성기(120)에 의해 생성된 키들(I₀, I₁, ...)을 수용한다. 입력 심볼들의 수는 미리 공지될 수도 그렇지 않을 수도 있다. 일부 실시예들에서는, 비-체계적 인코더(130)가 각각의 키(I)에 대해 하나의 출력 심볼을 생성한다. 도 1A에서, 출력은 키들(I₀, I₁, ...)에 대응되는 B(I₀), B(I₁), ...으로 지시된다. 생성된 출력 심볼들의 수는 잠재적으로 무한이다. 키 생성기(120)는, 키 생성기(120)가 그것으로부터 키들을 생성하는 난수 생성기로의 액세스를 가질 수 있다. 다른 방법으로, 어떠한 다른 메커니즘에 의해 키들(I)이 생성될 수도 있다. 인코더(130)는, 예를 들어, Raptor에서 설명된 바와 같은, 정적 및 동적 인코더들을 포함할 수 있다. 인코더(130)는 정적 인코더를 설명하는데 사용되는 추가적인 키 생성기로의 액세스를 가질 수도 있다.

Luby I 및 Raptor를 참조하면, 입력 심볼들로부터 출력 심볼들을 획득하기 위한 다양한 방법들이 존재한다. 이러한 인코딩 방법의 일 실시예가 도 2에 제시되어 있다. 도 2는 원래 입력 심볼들로부터의 출력 심볼(270) 생성을 설명한다. 원래 입력 심볼들은 210(a)-210(f)로 지시된다. 일부 실시예들에서, 코딩 프로세스의 제 1 단계는, Raptor에서 설명된 바와 같은, 정적 인코딩이다. 이 단계는, 220(a)-220(f) 및 260(a)-260(c)로서 지시되는 소스 심볼들을 발생시킬 수 있다. 일부 실시예들에서는, 정적 인코딩이 체계적일 수 있으므로, 소스 심볼들(220(a)-220(f))의 값들이 210(a)-210(f)의 값들과 동일할 수도 있다. 일부 실시예들에서는, 정적 인코딩이 없을 수도 있는데, 이 경우에는, 입력 심볼들이 소스 심볼들과 일치한다. 소스 심볼들은, 데이터 심볼들이 이용될 수 있을 때, 오프라인으로 또는 온라인으로 발생될 수 있다.

소스 심볼들이 생성되고 나면, 소스 심볼들로부터 출력 심볼들이 생성된다. 일부 실시예들에서, 출력 심볼의 값은 일부 소스 심볼들의 값들에 대한 XOR이다. 각각의 출력 심볼에 대해, 키 생성기(120)는 키를 발생시키는데, 키에 의해, 가중치 도표(250)로부터 출력 심볼의 가중치가 판정된다. 가중치(W)가 판정되고 나면, W개의 랜덤 또는 의사 랜덤 소스 심볼들이 선택되고, 이러한 소스 심볼들의 값들에 대한 XOR로서 출력 심볼의 값이 계산된다. 예를 들어, 도 2에서, 출력 심볼(270)의 가중치는 3이고, 출력 심볼(270)의 값은 소스 심볼들(220(a), 220(d), 및 260(b))의 XOR로서 판정된다. 출력 심볼의 가중치를 이 문서에서는 간혹 출력 심볼의 차수(degree)라고도 한다. 소스 심볼(S)이 출력 심볼(O)의 값에 기여한다면, S와 O는 이웃이라고 한다. 예를 들어, 도 2에 도시된 상황에서, 출력 심볼(270)은 소스 심볼들(220(a), 220(d), 및 260(b)) 각각의 이웃이다.

도 1B의 연쇄 반응 디코더(170)의 다양한 실시예들이 Luby I 및 Raptor에 상세히 설명되어 있다. 일부 실시예들에서는, 충분한 출력 심볼들이 수집되기만 하면, 디코딩 프로세스가 시작된다. 일부 실시예들에서는, 수집된 출력 심볼들의 수가 원래 입력 심볼들의 수보다 약간 더 크다. 다른 실시예들에서는, 디코딩 프로세스를 시작하기데 필요한 수집된 출력 심볼들의 수가 원래 입력 심볼들의 수보다 훨씬 더 작을 수도 있다.

일부 실시예들에서는, 수신된 각각의 출력 심볼에 대해, 키 생성기(160)가 심볼에 대한 대응 키를 계산하고, 키로부터, 이웃한 소스 심볼들을 판정한다.

연쇄 반응 디코딩을 위한 디코딩 프로세스의 일 실시예에 대한 가능한 일 설명이, 도 3에 예시적으로 도시되어 있는 바와 같은, 대응되는 디코딩 그래프의 관점에서 설명될 수 있다. 이 그래프는, 각각, 소스 심볼들 및 수신된 출력 심볼들에 대응되는, 소스 노드들 및 출력 노드들의 2개 세트로 이루어진다. 소스 노드들은 소스 심볼들에 대응되고, 마찬가지로 출력 노드들은 출력 심볼들에 대응된다. 소스 노드에 대응되는 소스 심볼이 출력 노드에 대응되는 출력 노드의 이웃이면, 출력 노드는 소스 노드에 접속된다. 이 경우, 상기 출력 노드 및 상기 소스 노드는 이웃이라고 한다.

일부 실시예들에서는, 차수 1의 출력 노드 O₁을 식별하는 것에 의해 디코딩 이 시작된다. 그 다음, O₁의 고유한 이웃은 복구된 것으로 선언되고 디코딩 그래프로부터 삭제되며, 차수 1의 다른 출력 노드 O₂를 식별하는 것에 의해, 프로세스는 계속된다. 예를 들어, 도 3에 도시된 상황에서, O₁은 330(a)로 지시된 출력 노드일 수 있다. 디코딩 그래프로부터 O₁의 고유한 이웃(320(b))를 삭제하는 것은 차수 1의 또 다른 출력 노드, 즉, 330(c)를 발생시킨다. 모든 소스 노드들이 복구되거나 남아 있는 차수 1의 출력 노드가 존재하지 않을 때까지, 프로세스는 계속된다.

예를 들어, 도 3의 상황에서는, 대응되는 소스 노드들을 복구하기 위해, 다음의 표 1과 같은, 출력 노드들의 시퀀스가 선택될 수 있다.

출력 노드	복구된 소스 노드
330(a)	320(b)
330(c)	320(e)
330(h)	320(h)
330(d)	320(i)
330(b)	320(a)
330(j)	320(f)
330(e)	320(c)
330(f)	320(g)
330(g)	320(d)

이 경우, 디코딩은 성공적이다.

일부 실시예들에서는, Luby I 또는 Raptor에서 예시된 바와 같은, 디코딩에 필요한 실제 계산들에 대한 스케줄을 설정하는데 그래프 해석을 사용할 수 있다. 또한, 상술된 이상적 디코더는 필요한 리소스들을 감소시키거나, 상술된 특허들 및 특허출원들에서 설명된 바와 같은, 디코딩 프로세스를 가속화하기 위해, 다양한 방식으로 변경될 수 있다.

일부 실시예들에서는, 디코더가, 대응되는 입력 노드들을 복구하는데 사용된 출력 노드들의 시퀀스를 출력할 수 있다. 예를 들어, 위에서 약술된 경우에서, 디코더는 출력 노드들(330(a), 330(c), 330(h), 330(d), 330(i), 330(b), 330(j), 330(e), 330(f), 및 330(g))에 대응되는 인덱스들을 출력할 수 있다.

간혹은 디코딩 그래프의 행렬 표현을 고려하는 것이 유리하며, 이러한 행렬의 관점에서 디코딩 알고리즘을 해석하는 것을 다음에서는 디코딩 행렬이라고 한다. 본 발명의 일부 실시예들에서, 디코딩 그래프에 대응되는 디코딩 행렬은 출력 노드들만큼의 로우들 및 소스 노드들만큼의 컬럼들을 가지며, 0 또는 1의 엔트리들을 가진다. j-번째 소스 노드가 k-번째 출력 노드의 이웃이면, 디코딩 행렬의 위치 (k, j)에 1이 존재한다.

도 4는 도 3의 디코딩 그래프에 대한 디코딩 행렬의 예시적 도면이다. 당업자라면 알 수 있는 바와 같이, 디코딩 문제는 디코딩 행렬에 의해 주어지는 방정식들의 시스템을 풀어내는 것으로 표현될 수 있다. M이 디코딩에 대응되는 디코딩 행렬을 지시하고, 출력 심볼들에 대한 값들의 벡터가 b로써 지시되며, K개의 소스 노드들이 존재한다면, 미지의 소스 심볼 값들(x₁, x₂, ..., x_k)은 다음의 행렬 방정식을 충족시키는데,

Mㆍx = b

여기서, x는 컬럼 벡터 (x₁, x₂, ..., x_k)이다. 결과적 행렬이 하삼각행렬(lower triangular matrix)이 되게 하는, 즉, 상기 행렬의 주대각선(main diagonal) 값들이 0이 되게 하는, M의 로우들과 컬럼들의 순열(permutation)이 존재한다면, 연쇄 반응 디코딩은 성공적이다. 예를 들어, M의 로우들에 대해 (3→2, 8→3, 2→5, 10→6, 5→7, 6→8, 7→9)의 순열을 수행하고 컬럼들에 대해 (2→1, 5→2, 8→3, 9→4, 1→5, 3→7, 7→8, 4→9)의 순열을 수행함으로써, 하삼각행렬이 발생된다. 행렬들의 관점에서 기술하자면, 이것은, 연쇄 반응 디코딩 알고리즘이, PㆍMㆍQ가 하삼각행렬이 되게 하는 순열 행렬들(permtation matrices;P 및 Q)을 발생시킨다는 것을 의미한다. 당업자들에게 공지되어 있는 바와 같이, 선형 방정식들의 시스템을 풀어내기 위한 다양한 방법들이 존재한다. 예를 들어, 가우스 소거 알고리즘이 사용될 수도 있다.

디코딩 행렬의 도면은 예시적인 목적을 위한 것일 뿐 한정적인 것이 아니다. 특히, 디코더의 실제 연산들은, Luby I, Raptor, 및 상술된 특허출원들에서 설명된 바와 같은, 선행 논의들과 실질적으로 상이할 수 있다.

일부 실시예들에서, Raptor에서 설명된 바와 같은, 다단의 연쇄 반응 코딩 시스템이 사용된다면, 디코딩 그래프는, 사용되는 특정한 정적 인코딩에 의해 주어지는 소스 심볼들간의 관계를 설명하는 2차 그래프에 의해 증대될 수 있다. 예를 들어, 정적 인코딩 프로세스에 저밀도 패리티-점검 코드(low-density parity-check code)가 사용된다면, 이 코드의 체크 심볼들 수와 동일한 다수의 출력 노드들이 디코딩 그래프에 부가되고, 그들의 값은 0으로 설정될 수 있으며, 디코딩 그래프는 소스 노드들과 체크 노드들간의 저밀도 패리티-체크 코드의 그래프에 의해 증대될 수 있고, 디코딩 그래프는 새로운 그래프로 대체될 수 있다. 저밀도 패리티-체크 코드들의 선택은 이 출원에서 본질적인 것이 아니다. 일반적으로, 임의 유형의 정적 인코딩의 경우, 대응되는 패리티-체크 행렬은, 그에 의해 디코딩 그래프가 증대될 수 있는 2분 그래프(bipartite graph)를 정의한다. 이러한 새로운 그래프를 다음에서는 변형된 디코딩 그래프(Modified Decoding Graph)라고 할 것이다.

도 5는 변형된 디코딩 그래프를 획득하기 위한 절차의 실시예이다. 소스 노드들은 510(a)-510(f)로 지시되고, 출력 노드들은 520(a)-520(g)로서 지시되며, 체크 노드들은 530(a)-530(d)로서 지시된다. 소스 노드들은 소스 심볼들에 대응된다. 출력 노드들과 소스 노드들간의 그래프가, 출력 노드들의 이웃 구조에 의해 주어지는, 디코딩 그래프이다. 체크 노드들과 소스 노드들간의 그래프는 소스 노드들간의 관계들을 설명한다. 예를 들어, 노드(530(a))는, 소스 노드들(510(a), 510(b), 510(e), 및 510(f))에 대응되는 소스 심볼들의 값들에 대한 XOR가 0이라는 것을 나타낸다.

변형된 디코딩 그래프는, 소스 노드들만큼의 컬럼들 및 출력 노드들과 체크 노드들의 합계 값만큼의 로우들을 가진, 0들 및 1들로 이루어진 변형된 디코딩 행렬에 대응된다. 따라서, 변형된 디코딩 행렬은, 하나는 출력 노드들에 대응되고 하나는 체크 노드들에 대응되는, 로우들의 2개 세트로 이루어진다. L개의 출력 노드들, C개의 체크 노드들, 및 K개의 소스 노드들이 존재하는 경우라면, 변형된 디코딩 행렬은 L개의 로우들과 K개의 컬럼들로 이루어진 부분 행렬 M₀ 및 C개의 로우 들과 K개의 컬럼들로 이루어진 행렬 M_c로 분해될 수 있다. x₁, ..., x_k가 소스 심볼들의 미지 값들을 지시하고, b₁, ..., b_k가 수신된 출력 심볼들의 공지 값들을 지시한다면, 디코더의 태스크는 M₀ㆍx = b 및 M_cㆍx = 0로써 주어지는 방정식들의 시스템을 풀어 내는 것일 수 있다. 방정식들의 조합된 시스템은 도 6으로 제시된 형태일 것이다.

연쇄 반응 디코더의 일부 실시예들에서는, 불활성화 디코더(Inactivation Decoder)라고 하는 상이한 디코더가 사용될 수 있다. 여기에서의 참고 문헌에 통합되어 있으며, "불활성화 디코더"라고 하는, "Systems and Process for Decoding a Chain Reaction Code through Inactivation"이라는 명칭으로 공동 출원된 계류 중인 미국 특허출원 제 10/459,370호에, 이러한 디코더가 보다 상세히 설명되어 있다.

Ⅱ. 체계적 연쇄 반응 인코더 & 디코더 및 연산 방법들

도 7A는 본 발명에 따른 체계적 연쇄 반응 코드들을 사용해 데이터를 인코딩하는 예시적 방법을 도시한다. 여기에서 사용되는 바와 같이, "출력 심볼(들)"이라는 용어는 연쇄 반응 코드를 의미하는데, 그것의 예들이 Luby I 및 Raptor에 설명되어 있다. 따라서, 체계적 및 비-체계적 출력 심볼들은 연쇄 반응 코드들의 특정 유형들로서, 체계적 출력 심볼은 전송된 입력 심볼을 구비하고, 비-체계적 출력 심볼은 하나 이상의 입력 심볼들의 함수인 출력 심볼들을 구비한다.

도 7A의 방법은, 인터넷, 텔레비전 전송기로부터 텔레비전 수신기로의 브로 캐스트 링크, 또는 한 점에서 다른 점으로의 전화 접속을 통한 경로와 같은, 실시간 채널 또는, 하나 또는 다수의 CD-ROM들, 다스크 드라이브들, 웹 사이트들 등과 같은, 저장 채널일 수 있는 통신 채널을 통한 전송을 위해 데이터를 인코딩하는 것과 같은, 다양한 애플리케이션들에 사용될 수 있다. 통신 채널은 심지어, 입력 파일을 퍼스널 컴퓨터로부터 전화선을 통해 ISP(Internet Service Provider)로 전송하여, 입력 파일이 웹 서버상에 저장된 다음 인터넷을 통해 수신자에게로 전송될 때 형성되는 채널과 같은, 실시간 채널과 저장 채널의 조합일 수도 있다.

이제 도 7A를 참조하면, 인코딩 프로세스는, 한 세트의 입력 데이터가 수신되고 그로부터 한 세트의 입력 심볼들이 생성되는 702에서 시작된다. 이 프로세스의 실시예들이 Luby I 및 Raptor에 설명되어 있기는 하지만, 본 발명에 따른 다른 실시예들에서는 다른 기술들이 사용될 수도 있다. 본 문서 및 여기에서 언급하거나 참조로써 통합되어 있는 문서들에 설명되어 있는 바와 같이, 입력 데이터는, 전체 세트가 미리 공지되지 않는 라이브 데이터를 포함하는, 임의의 포맷 및 유형일 수 있다.

다음으로, 입력 심볼들로부터 하나 이상의 비-체계적 출력 심볼들이 생성된다. 그러한 프로세스의 특정 실시예에서는, 입력 심볼들로부터 먼저 중간 입력 심볼들이 생성된다(704). 다음으로는, 중간 입력 심볼들로부터 하나 이상의 비-체계적 출력 심볼들이 생성된다(706). 본 발명에 따른 다른 실시예들에서는, 706의 프로세스가 생략되고 입력 심볼들로부터 비-체계적 출력 심볼들이 생성될 수도 있다. 이러한 프로세스들 각각이 다음에 보다 상세히 도시되어 있다.

다음에서 부연되는 바와 같이, 입력 심볼들은 입력 데이터에 대한 입력 심볼 생성기에 의해 제공된다. 상술된 바와 같이, 입력 데이터는, 비디오 캡처 모듈과 같은, 이차 장치로부터 실시간으로 획득된 데이터일 수 있으며, 또는, 예를 들어, 입력 데이터가 이차 애플리케이션에 의해 생성된 파일 또는 버퍼에 상주하는 경우, 입력 데이터는 정적일 수 있다. 본 발명의 다른 애플리케이션에서는, 입력 데이터가 실시간과 정적 방법의 조합에 의해, 예를 들어, 네트워크 카드와 같은, 이차 장치 또는 애플리케이션으로부터 데이터를 수신하고 그것을 입력 심볼 생성기에 의한 추가적인 프로세싱을 위해 저장 장치에 저장하는 것에 의해, 획득될 수도 있다.

도 7B는 본 발명에 따라 체계적 연쇄 반응 코드들을 디코딩하는 예시적 방법을 도시한다. 처음에 712에서는, 입력 심볼들의 제 1 세트가 획득된다. 애플리케이션은 통상적으로, 이 프로세스가 실현되는 방법을 판정할 것이다. 예를 들어, 통신 시스템에서 사용될 경우, 이 프로세스는, 통신 채널을 통해 전송된 연쇄 반응 코드들의 입력 심볼들을 수신하는 것에 의해, 수행된다. 상술된 바와 같이, 본 발명의 특정 실시예들에서, 통신 채널은 실시간 채널, 저장 채널, 또는 그들의 조합일 수 있다. 다음에서 부연되는 특정 실시예에서는, 체계적 출력 심볼들을 구비하는 입력 심볼들을 수신기로 전송하는 것에 의해, 입력 심볼들의 포착이 실현된다. 예상되는 채널 손실들 때문에, 전송된 입력 심볼들(즉, 체계적 출력 심볼들) 중 일부는 손실될 수 있다. 따라서, 입력 심볼들의 원래 세트에 대한 서브세트만이 수신기에 의해 획득될 수 있다.

다음으로 714에서는, 하나 이상의 비-체계적 출력 심볼들이 획득된다. 다른 실시예들에서는 다른 수단들이 사용될 수 있지만, 통상적으로, 비-체계적 출력 심볼들의 획득은 입력 심볼들과 동일한 방식을 따를 것이다.

본 방법은, 획득되지 않은 하나 이상의 입력 심볼들이 복구되는 716에서 계속된다. 이 프로세스의 특정 실시예에서는, 누락된 입력 심볼들이, 비-체계적 출력 심볼들로부터 또는 비-체계적 출력 심볼들과 획득된 입력 심볼들의 조합으로부터, 복구될 수 있다.

716에서의 복구 프로세스는 하나의, 수개의, 또는 누락된 입력 심볼들 모두를 복구하는데 사용될 수 있다. 소정 갯수의 누락된 입력 심볼들이 복구되고 나면, 이들은 획득된 입력 심볼들에 추가되어 입력 심볼들의 원래 세트 및 그에 따른 원래 데이터의 복사본을 재편성할 수 있다.

도 7C는 본 발명의 일 실시예에 따른 체계적 코딩 및 디코딩을 사용하는 예시적 통신 시스템(700)의 블록도이다. 통신 시스템(700)에서, 입력 파일(721) 또는 입력 스트림(725)이 입력 심볼 생성기(726)에 제공된다. 입력 심볼 생성기(726)는 입력 파일 또는 스트림으로부터, 각각이 값 및 (도 7에서 괄호 속의 정수로서 지시되는) 위치를 갖는 하나 이상의 입력 심볼들의 시퀀스(IS(0), IS(1), IS(2), ...)를 생성한다. 상술된 바와 같이, 입력 심볼들에 대해 가능한 값들, 즉, 그것의 알파벳은 통상적으로 2^M개 심볼들의 알파벳이므로, 각각의 입력 심볼은 입력 파일의 M개 비트들을 코딩한다. M의 값은 일반적으로 통신 시스템(700)의 용도에 의해 판정되지만, 범용 시스템은 입력 심볼 생성기(726)에 대한 심볼 크기 입력 을 포함할 수 있으므로, M은 용도에 따라 달라질 수 있다. 입력 심볼 생성기(726)의 출력은 체계적 인코더(728)에 제공된다.

비-체계적 키 생성기(727)는 인코더(728)로 제공된 입력 심볼들에 대응되는 키들(I₀, I₁, I₂, ...)을 생성하는데, 비-체계적 키들은 인코더(728)로부터 출력되는 비-체계적 출력 심볼들(B(I₀), B(I₁), B(I₂), ...)의 값들을 계산하는데 사용된다. 각각의 비-체계적 키(I₀, I₁, I₂, ...)는, 동일한 입력 파일에 대한 키들의 대부분이 고유하도록 생성된다. 다른 실시예들에서는 비-체계적 키들을 생성하도록 동작될 수 있는 다른 유형의 장치가 사용될 수 있지만, 일 실시예에서, 비-체계적 키 생성기(727)는, 상기 도 1A에 도시되고 Luby I 및 Raptor에서 설명된, 키 재생기(120)를 구비한다.

체계적 키 생성기(730)는 인코더(728)로 제공된 입력 심볼들에 대응되는 체계적 키들(C₀, C₁, C₂, ...)를 생성하는데, 이 키들은, 다음에서 부연되는 바와 같이, 수신되지 않은 하나 이상의 입력 키들을 복구하는데 사용될 수 있다. 체계적 키 생성기(730)는 키들을 생성하기 위해 난수 생성기(735)에 의해 생성된 난수들을 사용할 수 있다. 다음에서는, 체계적 키들의 생성을 보다 상세히 후술한다. 비-체계적 키 생성기(727) 및 체계적 키 생성기(730)의 출력들은 인코더(728)에 제공된다.

비-체계적 키 생성기(727)에 의해 제공되는 각각의 비-체계적 키(I) 및 입력 심볼 생성기에 의해 제공되는 입력 심볼들로부터, 인코더(728)는 값 B(I)를 가진 비-체계적 출력 심볼을 생성한다. 생성된 비-체계적 출력 심볼은 Luby I(일단 인코딩/디코딩)에서 설명된 출력 심볼이거나 Raptor(다단 인코딩/디코딩)에서 설명된 출력 심볼일 수 있다. 예시적인 체계적 인코더(728)의 연산은 다음에서 부연될 것이다. 출력 심볼 각각의 값은 그것의 키 및 하나 이상의 입력 심볼들의 소정 함수에 기초해 생성된다.

일부 실시예들에서, 입력 심볼들의 갯수 K는 체계적 인코더(728)에 의해 동료들을 선택하는데 사용된다. 입력이 스트리밍 파일인 경우와 같이, K가 미리 공지되어 있지 않다면, K는 단순한 추정치일 수 있다. 또한, 값 K는 입력 심볼들 및 체계적 인코더(728)에 의해 생성되는 임의의 중간 심볼들에 대한 저장 공간을 할당하는데도 사용될 수 있다.

체계적 인코더(728)는 체계적 키들(C₀, C₁, ..., C_k-1)과 함께 입력 심볼들(IS(0), IS(1), ...)을 전송 모듈(740)로 전달하거나 체계적 키들을 재생하는 방법에 관한 지시를 전송 모듈(740)로 전달한다. 전송될 때, 심볼들(IS(0), IS(1), ...)을 여기에서는 "체계적 출력 심볼들"이라고 한다. 체계적 인코더(728)는, 입력 심볼들을 전송 모듈로 전달하기 전에 추가적인 출력 심볼들의 생성을 위해 입력 심볼들의 복사본을 생성할 수 있다.

체계적 인코더(728)는 비-체계적 출력 심볼들(B(I₀), B(I₁), B(I₂), ...)도 전송 모듈(740)에 제공한다. 또한, 전송 모듈(740)에는 비-체계적 키 생성기(727)로부터의 이러한 출력 심볼 각각에 대한 비-체계적 키들(I₀, I₁, I₂, ...)도 제공된 다. 전송 모듈(740)은 체계적 및 비-체계적 출력 심볼들을 전송하며, 사용되는 편이 방법(keying method)에 따라, 전송 모듈(740)은 전송된 출력 심볼들의 키들에 관한 소정 데이터를 채널(745)을 통해 수신 모듈(750)로 전송할 수도 있다. 채널(745)은 소실 채널인 것으로 가정되지만, 이것이 통신 시스템(700)의 적합한 연산을 위한 요구 사항인 것은 아니다. 모듈들(740, 745, 및 750)은, 전송 모듈(740)이 출력 심볼들 및 그들의 키들에 관한 임의의 필요 데이터를 전송하도록 적응되고 수신 모듈(750)이 채널(745)로부터 심볼들 및 그들의 키들에 관한 잠재적인 소정 데이터를 수신하도록 적응되기만 한다면, 적합한 임의의 하드웨어 컴포넌트들, 소프트웨어 컴포넌트들, 물리적 매체, 또는 그들의 임의 조합일 수 있다. K의 값은, 동료들을 판정하는데 사용된다면, 채널(745)을 통해 송신될 수 있고, 또는 인코더(728)와 디코더(755)의 협정에 의해 미리 설정될 수도 있다.

상술된 바와 같이, 채널(745)은, 인터넷, 텔레비전 전송기로부터 텔레비전 수신기로의 브로드캐스트 링크, 한 점으로부터 다른 점으로의 전화 접속이 통과하는 경로와 같은, 실시간 채널이거나, CD-ROM, 디스크 드라이브, 웹 사이트 등과 같은, 저장 채널일 수도 있다. 심지어 채널(745)은, 입력 파일을 퍼스널 컴퓨터로부터 전화선을 통해 ISP로 전송하여, 입력 파일이 웹 서버상에 저장된 다음, 인터넷을 통해 수신자에게로 전송되는 경우에 형성되는 채널과 같은, 실시간 채널과 저장 채널의 조합일 수도 있다.

수신 모듈(750)은 채널(745)로부터 비-체계적 및/또는 체계적 출력 심볼들을 수신하여 그것을 디코더(755)에 공급한다. 수신된 출력 심볼들의 키들에 대응되는 데이터는 비-체계적 키 재생기(760) 및 체계적 키 재생기(780)로 제공된다. 도 7의 도시된 실시예에서는, IS(x), IS(y), ..., IS(z)로써 지시되는 한 세트의 체계적 출력 심볼들이 비-체계적 출력 심볼들의 세트(B(I_a), B(I_b), B(I_c), ...)와 함께 수신된다. 다른 실시예들에서는, 수신 모듈(750)이 체계적 출력 심볼들만을 배타적으로 수신하거나, 체계적 심볼들과 비-체계적 심볼들의 조합을 수신할 수도 있다.

비-체계적 키 재생기(760)는 수신된 비-체계적 출력 심볼들에 대한 비-체계적 키들을 재생하고 이 키들을 체계적 디코더(755)에 제공한다. 다른 실시예들에서는 비-체계적 키들을 재생하도록 동작할 수 있는 다른 유형의 장치가 사용될 수도 있지만, 일 실시예에서, 비-체계적 키 재생기(760)는, 상기 도 1B에 도시되고 Luby I 및 Raptor에서 설명된, 키 재생기(160)를 구비한다. 체계적 키 재생기(780)는 체계적 키들(C₀, C₁, ...)을 재생하여 이들을 체계적 디코더(755)에 제공한다. 체계적 키 재생기(780)는, 체계적 키들의 재생을 용이하게 하는, 체계적 키 생성기(730)와의 소정 공유 정보로의 액세스를 가질 수 있다. 다른 방법으로, 체계적 키 재생기(780)는 채널(745)을 통해 전송된 추가적인 정보에 기초해 키들을 재생할 수도 있다. 일부 실시예들에서는, 체계적 키 재생기(780)가, 체계적 키들을 생성하는데도 사용될 수 있는 동일한 난수 생성기(735)로의 액세스를 가질 수도 있다. 이것은, 난수들이 이러한 장치에서 생성되는 경우라면, 동일한 물리적 장치로의 액세스 형태이거나, 동일한 동작을 실현하기 위해 난수들을 생성하는 동일한 알고리즘으로의 액세스 형태일 수도 있다.

디코더(755)는, 입력 심볼들(역시 IS(0), IS(1), IS(2), ...)을 복구하기 위해, 대응되는 출력 심볼들과 함께, 비-체계적 키 재생기(760) 및 체계적 키 재생기(780)에 의해 제공되는 비-체계적 키들을 사용한다. 복구된 입력 심볼들은 입력 파일 리어셈블러(765)로 전달된다. 체계적 디코더(755)는, 나머지 입력 심볼들을 복구하기 전에, 수신된 체계적 출력 심볼들(IS(x), IS(y), ..., IS(z))을 입력 파일 리어셈블러(765)로 직접 전달할 수도 있다. 특히, 모든 입력 심볼들이 수신되었다면, 디코더는, 추가적인 계산없이, 수신된 데이터를 단순히 입력 파일 리어셈블러로 전달하는 것을 선택할 수도 있다. 입력 파일 리어셈블러(765)는 입력 파일(721) 또는 입력 스트림(725)의 복사본(770)을 생성한다.

다음에서는, 체계적 인코더(728) 및 디코더(755)의 연산들을 보다 상세히 설명할 것이다. 본 발명의 일부 실시예들에서, 이러한 유닛들은, 상술된 바와 같은, 연쇄 반응 인코딩 및 디코딩을 사용할 수 있다.

도 8A는 본 발명의 특정 실시예에서의 체계적 인코더(728) 연산을 도시한다. 처음에는, 체계적 인코더(728)가 도 7의 입력 심볼 생성기(726)로부터 입력 심볼들(IS(0), IS(1), ..., IS(K-1))을 수신한다. 입력 심볼들은, 인코딩을 시작할 때, 그 전부가 공지이거나 일부만이 공지일 수 있다.

이 실시예에서는, 체계적 인코더(728)가, 생성된 비-체계적 출력 심볼들의 갯수만큼 비-체계적 키들(I₀, I₁, ...)을 생성하는 비-체계적 키 생성기(727)로의 액세스를 가진다. 또한, 체계적 키 생성기(730)는 존재하는 입력 심볼들만큼의 체계적 키들(C₀, C₁, ..., C_K-1)을 생성한다. 체계적 인코더(728)는 원래 입력 심볼들을 체계적 출력 심볼들로서 전송 모듈(750)로 전달한다. 또한, 체계적 인코더(728)는 비-체계적 키 생성기(720)에 의해 생성된 키들(I₀, I₁, ...) 각각에 대해 비-체계적 출력 심볼들(B(I₀), B(I₁), ...)을 생성하도록 동작한다. 체계적 키 생성기(730)의 연산은 다음에서 부연된다.

체계적 키 생성기(730) 및 체계적 키 재생기(780;도 7)는, 체계적 키 재생기(780)가 체계적 키 생성기(730)와 동일한 키들을 생성하는데 성공할 수 있도록 하기 위해, 소정 공유 정보로의 액세스를 가질 수 있다. 일부 실시예들에서는, 공유 정보가 체계적 키 재생기(780)로 전송될 수도 있다. 다른 실시예들에서는, 체계적 키들이 코드의 다른 파라미터들, 예를 들어, 입력 심볼들의 수 및 가중치 도표의 결정 함수(deterministic function)일 수 있다.

일부 실시예들에서는, 입력 심볼들 수의 일부 또는 모든 관련 값들에 대해 체계적 키들이 미리-계산되어 있을 수 있다. 일부 실시예들에서는, 체계적 키들이 입력 심볼들의 상이한 세트들에 대해 재사용될 수도 있다. 다른 실시예들에서는, 체계적 키 생성기(730)와 체계적 키 재생기(780)간의 소정 공유 정보를 사용해, 체계적 키들이 모든 입력 블록에 대해 재계산될 수도 있다.

도 8B는 본 발명의 특정 실시예에서의 체계적 디코더(755) 연산을 도시한다. 체계적 디코더(755)는 수신 모듈(750)로부터, 각각, IS(x), IS(y), ..., IS(z) 및 B(I_a), B(I_b), ...로서 지시된 체계적 및 비-체계적 출력 심볼들을 수신한다. 특정 실시예에서, 체계적 디코더(755)는 체계적 키 재생기(780) 및 비-체계적 키 재생기(760)로의 액세스를 가진다. 체계적 연쇄 반응 디코더의 출력은 초기 입력 심볼들의 세트(IS(0), IS(1), ..., IS(K-1))이다.

도 9A는 체계적 인코더(728)를 보다 상세하게 도시한다. 체계적 인코더(728)는 연쇄 반응 디코더(910) 및 연쇄 반응 인코더(920)를 포함한다. 또한, 체계적 인코더(728)는 중간 심볼들(S(0), S(1), ..., S(K-1))을 저장하기 위해 (나타내지 않은) 메모리 장치로의 액세스를 가질 수도 있다.

입력 심볼들(IS(0), IS(1), ..., IS(K-1)) 및 체계적 키들(C₀, C₁, ..., C_K-1)의 수신시에, 연쇄 반응 디코더(910)는, 예를 들어, 여기에 통합되어 있는 특허들 및 특허출원들에 설명되어 있는, 연쇄 반응을 위한 디코딩 방법들을 사용해, 한 세트의 중간 입력 심볼들(S(0), S(1), ..., S(K-1))을 계산한다. 본 발명의 일부 실시예들에서는, 중간 입력 심볼들이 메모리 또는 디스크에 저장될 수 있다. 다른 실시예들에서, 중간 입력 심볼들은, 그들이 이용될 수 있을 때, 연쇄 반응 인코더(920)로 전달될 수 있다.

연쇄 반응 인코더(920)는, 비-체계적 출력 심볼들(B(I₀), B(I₁), ...)을 생성하기 위해, 비-체계적 키 생성기(727)에 의해 생성된 비-체계적 키들(I₀, I₁, I₂, ...)과 함께 연쇄 반응 인코더(910)에 의해 생성된 중간 입력 심볼들을 사용한다. 일부 실시예들에서, 이러한 인코딩 프로세스는, 본 발명의 중간 입력 심볼들이 Luby I의 입력 심볼들로서 사용된다는 것이 변경된 상태로서, Luby I 또는 Raptor에서 설명된 입력 심볼 인코딩 프로세스를 사용해 실현될 수 있다. 특정 실시예에서는, 비-체계적 출력 심볼들이 입력 심볼들(IS(0), IS(1), ..., IS(K-1)) 이후에 전송 모듈(140)로 공급된다. 그러나, 이것이 본 발명의 동작을 위해 필수적인 것은 아니다. 또한, 전송 모듈(740)로부터의 전송 순서 또한 달라질 수 있다.

도 9B는 연쇄 반응 디코더(930) 및 연쇄 반응 인코더(940)를 포함하는 체계적 디코더(755)의 실시예이다. 체계적 디코더로의 입력은 수신된 출력 심볼들을 포함하는데, 그들 중 일부는 수신된 체계적 출력 심볼들(IS(x), IS(y), IS(z), ...)을 구비하고 그들 중 일부는 수신된 비-체계적 출력 심볼들(B(I_a), B(I_b), ...)을 구비할 수 있다. 일부 실시예들에서는, 디코더가 수신된 체계적 심볼들을 메모리 장치에 복사할 수 있고, 이들을 입력 파일 리어셈블러(765)로 직접 전달할 수 있다.

연쇄 반응 디코더(930)는, 중간 입력 심볼들(S(0), S(1), ..., S(K-1))을 발생시키기 위해, 심볼들(IS(x), IS(y), ..., IS(z), B(I_a), B(I_b), ...), 체계적 키 재생기(780)에 의해 생성된 체계적 키들(C_x, C_y, ..., C_z), 및 비-체계적 키 재생기(760)에 의해 생성된 비-체계적 키들(I_a, I_b, ...)을 사용한다. 체계적 키들(C_x, C_y, ..., C_z)은 수신된 입력 심볼들(IS(x), IS(y), ..., IS(z))에 대응된다. 일부 실시예들에서는, 복구된 중간 심볼들이 연쇄 반응 인코더(440)로 전달되기 전에 이 차 저장 장치에 저장될 수 있다. 다른 실시예들에서는, 이러한 중간 심볼들이 연쇄 반응 인코더(940)로 직접 전달될 수 있다.

연쇄 반응 인코더(940)는, 누락된 원래 입력 심볼들(IS(u), IS(v), ..., IS(w))를 생성하고 출력하기 위해, 소실된 체계적 출력 심볼들(IS(u), IS(v), ..., IS(w))에 대응되는 중간 입력 심볼들 및 체계적 키들(C_u, C_v, ..., C_w)을 사용한다. 예시적 실시예로서, 초기 키들(C_u, C_v, ..., C_w) 각각에 대해, 디코더는, 체계적 키들(C_u, C_v, ..., C_w)에 대응되는 소실된 입력 심볼들(IS(u), IS(v), ..., IS(w))을 획득하기 위해, 가중치 W 및, 중간 입력 심볼들(S(0), ..., S(K-1)) 중에서 W개 심볼들을 식별하고, 출력 심볼들의 XOR 값들을 식별한다. 일 실시예에서, 연쇄 반응 인코더(940)에 의해 사용되는 계산 리소스들의 양은 소실된 체계적 출력 심볼들의 수에 비례할 것이다. 예를 들어, 체계적 출력 심볼들 모두가 수신되었다면, 디코더는 어떤 계산도 수행하지 않고, 수신된 심볼들을 입력 파일 리어셈블러(765)로 전달할 수 있다.

특정 실시예들에서, 연쇄 반응 인코더(940) 및 연쇄 반응 디코더(910)는 동일한 가중치 도표로의 액세스를 가질 것이고, 정적 인코딩이 사용된다면, 동일한 정적 인코딩/디코딩을 사용할 것이다. 마찬가지로, 연쇄 반응 인코더(920) 및 연쇄 반응 디코더(930)도 동일한 가중치 도표로의 액세스를 가질 것이고, 동일한 정적 인코딩/디코딩을 사용할 것이다.

체계적 키들을 계산하기 위한 방법들

본 발명의 특정 실시예에서는, 체계적 키들이 심볼 전송 이전에 체계적 키 생성기(730)에 의해 계산되고, 심볼 수용 이후에 체계적 키 재생기(780)에 의해 재계산된다. 체계적 키들은 연쇄 반응 디코더(910) 및 인코더(930)에 의해 중간 입력 심볼들(S(0), S(1), ..., S(K-1))을 획득하는데 사용된다.

본 발명의 특정 실시예들에서는, K개 심볼들의 고유하고 효율적인 연쇄 반응 디코딩이 체계적 키들로써 생성된 정확히 K개의 출력 심볼들을 사용해 가능할 수 있는 방식으로, 체계적 키들이 계산된다. 이 경우, 디코딩은 Luby I, Raptor, 또는 불활성화 디코딩에서 설명된 디코딩 방법들, 또는 예를 들어 불활성화 디코딩에서 설명된 것과 같은 가우스 소거 알고리즘에 기초하는 좀더 일반적인 디코딩 방법들 중 어느 하나일 수 있다.

도 10은 체계적 키 생성 프로세스의 실시예이다. 체계적 키 생성기로의 일 입력은 입력 심볼들(IS(0), IS(1), ..., IS(K-1))의 갯수(K)일 수 있다. 변수 j를 0으로 설정하는 것에 의해, 체계적 키 생성이 시작된다. 알고리즘 동안, K개 컬럼들 및 처음에 0개의 로우를 가진 행렬(M)은, 알고리즘이 진행됨에 따라 로우들을 추가함으로써, 업데이트된다. j의 상이한 모든 값들에 대해, 알고리즘은 1020에서 상이한 키(D(j))를 생성한다. 이 키는 Luby I 또는 Raptor에서 설명된 방법들에 의해 생성될 수 있고, 도 1에 나타낸 난수 생성기(135)를 사용할 수도 있다. 다음으로 1030에서는, 키(D(j))를 사용해 행렬(M)의 j-번째 로우에 대한 엔트리들을 계산한다. 이러한 계산의 가능한 일 실시예가 연쇄 반응 코딩 프로세스에 키(D(j))를 사용하는 것이다. 이 경우, 가중치 도표를 사용해, 키(D(j))는 가중치(W) 및, 값들(0, 1, ..., K-1) 중에서 W개 값들을 식별한다. 다음으로, m이, 생성된 랜덤 또는 의사 랜덤 값들 중 하나라면, M의 j번째 로우 중 위치 m은 1로 설정되고 j번째 로우의 나머지 값들은 0으로 설정될 수 있다.

1040에서는, 현재 구성된 행렬(M)이, 곱셈 및 덧셈이 정수 2의 모듈로(modulo)로 수행되는, 0과 1로 이루어진 세트를 의미하는 2진 필드(GF(2))에 대해, 선형적으로 독립적인 K개의 로우들을 갖는지의 여부에 관한 판정이 이루어진다. 1040에서의 이 프로세스는 다양한 방식으로 수행될 수 있다. 예를 들어, 2진 필드(GF(2))에 대한 가우스 소거가 이것을 체크하는데 사용될 수 있다. 그러나, 당업자들에게 공지되어 있는 여타의 많은 방법들이 존재한다. 예를 들어, 불활성화 디코딩의 내용들이 행렬(M)에 적용된다면, M은, M에 적용된 불활성화 디코더가 성공적일 경우에만 선형적으로 독립적인 K개의 로우들을 포함한다.

1040에서의 테스트가 긍정적이고 M의 로우들(r(0), r(1), ..., r(K-1))이 선형적으로 독립적인 것으로 밝혀지면, 체계적 키들(C₀, C₁, ..., C_K-1)은 키들(D(r(0)), ..., D(r(K-1)))로 설정되고 이 키들이 출력된다. 1040에서의 테스트가 부정적이면, 1060에서 카운터(j)가 증가되고, 계산은 1020으로부터 반복된다.

당업자들에 의해 체계적 키들을 생성하는 등가의 또는 실질적으로 유사한 여타의 방법들이 고안될 수 있다. 예를 들어, 알고리즘이 수행되는 동안 한번에 하나씩 키들(D(j))을 생성하는 대신에, 이러한 키들의 세트(L)를 미리 생성한 다음, 알고리즘의 j 단계에서 이러한 키들의 풀로부터 키(D(j))를 취할 수도 있다. 이 경우, L은 입력 심볼들 수의 함수일 수 있다.

체계적 키들을 생성하기 위한 제 2 방법이 도 11에 예시되어 있다. 이 방법에서는, 이러한 알고리즘으로의 입력이 입력 심볼들의 수(K) 및, 통상적으로 K 이상인 숫자 L로 이루어진다. 일부 실시예들에서, L은, Luby I 또는 Raptor에서 설명된 바와 같이, 높은 확률로, 디코딩이 성공적이라는 것을 보장하기 위해 수집되어야 하는 출력 심볼들의 갯수일 수 있다.

1110에서는, L개의 키들(D(0), ..., D(L-1))이 생성된다. 이 프로세스는 난수 생성기(735)를 사용해 실현될 수 있다. 다른 실시예들에서는, 이러한 키들이 재사용 가능한 키들의 고정 리스트로부터 생성될 수도 있다. 또한, 이 프로세스는, 키들이 어떻게 생성되었는지에 관한 지시도 제공할 수 있다. 예를 들어, 난수 생성기가 사용되었다면, 생성기에 대한 시드(seed)는 체계적 키 생성기에 의한 장차의 사용을 위해 기록될 수 있다.

키들(D(0), ..., D(L-1))을 사용해, 1120에서는, 도 5에서 상술되고 예시된 바와 같은, 변형된 디코딩 그래프가 설정된다. 이 프로세스는 코드에 대한 특정 가중치 도표의 지식 뿐만 아니라, Raptor에서 설명된 바와 같은, 사용되는 임의의 정적 인코딩에 대한 지식도 이용할 수 있다.

1130에서는, 변형된 디코딩 그래프가 앞서 제시된 방법들 중 하나를 사용해 디코딩된다. 디코딩의 부산물로서, 입력 노드의 복구를 트리거하는 출력 노드들의 인덱스들(r(0), r(1), ..., r(K-1))이 기록된다. 1140에서는, 체계적 키들이 C₀=D(r(0)), ..., C_K=D(r(K-1))로서 출력된다.

도 12는 체계적 키들을 계산하기 위한 제 3 방법을 도시한다. 도 11의 방법과 마찬가지로, 1210에서는 키들(D(0), ..., D(L-1))이 생성되고, 이 키들 및 어쩌면 가중치 도표를 사용해 디코딩 그래프가 설정된다. 다음으로는, 1230에서 세트 S가 공백 세트로 초기화된다. 세트 S는, 입력 노드의 값을 복구하기 위해 연쇄 반응 디코딩 프로세스에 사용되는 출력 심볼들의 인덱스들을 포함할 것이다. 1240에서는, 차수 1의 출력 노드를 식별하는 것에 의해, 연쇄 반응 디코딩 프로세스가 디코딩 그래프에 적용된다. 이러한 출력 노드의 인덱스는 이 세트의 상술된 역할에 따라 세트 S에 추가된다. 1250에서는, 세트 S가 이미 적당한 갯수의 요소들을 가지고 있는지의 여부에 관한 테스트가 수행된다. 그렇지 않다면, 알고리즘은, 디코딩 프로세스를 계속하기 위해 차수 1의 다른 입력 노드가 선택되는 1240으로 역루핑한다. S의 크기가 K라면, 1260에서는, S의 요소들을 최소 요소로 시작해서 정렬하여 정렬된 요소들(S₀, ..., S_K-1)을 산출하며 C₀=D(S₀), ..., C_K-1=D(S_K-1)로서 체계적 키들이 계산된다.

도 13은, 본 발명에 따른, 체계적 키들을 계산하는 제 4 방법을 도시한다. 이 방법에서는, K 및 키들의 세트가 입력될 때, 주어진 키들의 세트로부터 원래의 K개 심볼들이 디코딩될 수 있는지의 여부를 판정할 수 있다면, 디코딩 알고리즘이 유효하다고 가정한다. Luby I, Raptor, 또는 불활성화 디코딩에서 설명된 디코더들에 의해, 이러한 알고리즘들의 예들이 제공된다.

1310에서는, 키들(D(0), ..., D(L-1))이 생성된다. 상기 설명과 마찬가지로, 이 프로세스는 난수 생성기(735)의 사용을 통해 실현되거나, 재사용 가능한 키들의 고정 세트로부터 키들이 생성될 수도 있다. 1315에서는, 디코더를 사용해, 키들의 세트(D(0), ..., D(L-1))로부터 K개 심볼들을 디코딩할 수 있는지의 여부를 판정한다. 디코딩이 성공적이지 않다면, 키들의 소정 세트는 체계적 키들의 서브세트를 포함하지 않으므로, 알고리즘은 1325에서 중단된다. 디코딩이 성공적이라면, 1330에서는 3개의 세트들이 초기화된다. 이러한 세트들을 각각 체계적(Systematic), 비_체계적(Non_Systematic), 및 무방문(Unvisited)이라고 한다. 알고리즘의 끝에서, 체계적 세트는 체계적 키들의 세트를 포함할 것이다. 원래, 1330에서는, 체계적 및 비_체계적 세트들이 공백 세트들로 초기화되는 한편, 무방문 세트는 원래의 모든 키들(D(0), ..., D(L-1))을 포함한다. 프로세스들(1335 내지 1360)에서는, 무방문 세트로부터 키가 삭제되고, 체계적 및 무방문 세트들에 포함된 키들에 대해 디코딩 시도가 이루어진다. 시도가 성공적이라면, 선택된 키(C)는 체계적 키들의 세트에 속하지 않는다. 반대로, 디코딩이 성공적이지 않다면, 키는 체계적 키들의 세트에 속한다. 체계적 세트가 원래 입력 심볼들의 수(K)보다 더 적은 수를 갖는 동안은, 무방문 키의 삭제 및 디코딩으로 이루어진 절차(1335), 디코딩이 성공적이었는지의 여부에 대한 테스트(1340), 및 디코더의 출력에 기초하는, 선택된 키의 체계적 또는 비_체계적 세트로의 후속적 추가(1345 및 1350)가 반복된다(1355).

도 14는 본 발명에 따른 체계적 및 비-체계적 심볼들을 가진 연쇄 반응 코드 를 디코딩하는 방법을 도시한다. 1410에서는, 수신된 비-체계적 출력 심볼들(B(I_a), B(I_b), ...)에 대응되는 비-체계적 키들(I_a, I_b, ...)이, 수신된 비-체계적 출력 심볼들만큼의 로우들 및 입력 심볼들만큼의 컬럼들을 가진 행렬 B를 생성하는데 사용된다. 각각의 키에 대해, 연쇄 반응 코드들을 인코딩하는 것과 동일한 메커니즘을 사용해, 가중치(W) 및, 그로부터 키에 대응되는 출력 심볼이 생성되는 입력 심볼들의 인덱스들 세트(J₁, J₂, ..., J_W)가 생성된다. 그 다음, 행렬 B의 대응되는 로우들에서, J₁, J₂, ..., J_W에 대응되는 위치들은 1로 설정되는 한편, 그 로우의 나머지 위치들은 0으로 설정된다. 수신된 비-체계적 심볼들에 대응되는 모든 키들이 소진될 때까지, 이 절차는 반복된다.

다음으로 1420에서는, 유사한 절차가, 체계적 키들(C₀, C₁, ..., C_K-1)로부터 입력 심볼들의 수와 동일한 로우들 및 컬럼들을 가진 정사각 행렬 C를 구성하는데 적용된다. 이 프로세스는 A라고 하는 행렬 C의 역도 계산한다. A의 역에 대한 계산은, 당업자들에게 공지되어 있는 다양한 방식으로 수행될 수 있다. 예를 들어, A를 계산하는데 가우스 소거 알고리즘이 사용될 수 있다. 다른 실시예들에서는, 이 단계를 수행하는데 연쇄 반응 디코딩 버전이 이용될 수 있다. 본 개시의 후속 예에서 이것이 부연된다.

1430에서는, 행렬 H를 얻기 위해, 2진 필드에 대해 행렬들(B 및 A)의 곱이 계산된다. 다음으로 1440에서는, 인덱스들의 2개 세트들(E 및 R)이 판정되는데, E는 수신된 비-체계적 심볼들의 인덱스들 세트인 반면, R은 수신된 체계적 심볼들의 인덱스들 세트이다. 예를 들어, 인덱스들(0, 1, 2, ..., 10)을 가진 11개의 입력 심볼들이 존재한다고 가정한다. 전송 이후에, 인덱스들(0, 3, 9, 10)에 대응되는 체계적 심볼들이 수신된다면, R={0, 3, 9, 10}이고 E={1, 2, 4, 5, 6, 7, 8}이다. 그 다음, 1430에서는 B와 A의 곱으로서 계산된 행렬 H가 2개의 부분 행렬들(H_E 및 H_R)로 분할되는데, H_E는 수신되지 않은 체계적 심볼들의 인덱스들에 대응되는 H의 컬럼들을 취하는 것에 의해 획득되는 H의 부분 행렬이고, H_R은 수신된 체계적 심볼들의 인덱스들에 대응되는 H의 부분 행렬이다. 상기 예에서, H_E는 H의 컬럼들(1, 2, 3, 4, 5, 6, 7, 및 8)에 의해 형성되는 H의 부분 행렬일 것이다.

1450에서는, 행렬 H_R이, 수신된 체계적 심볼들(IS(x), IS(y), ..., IS(z))에 의해 형성되는 벡터와 곱해진다. 예를 들어, 상기 시나리오에서는, H_R이 체계적 심볼들(0, 3, 9, 10)의 값들과 (이 순서로) 곱해질 것이다. 실제 곱셈은, 당업자들에게 공지되어 있는 바와 같은, 다양한 방식으로 수행될 수 있다. 다음에서 벡터 y라고 하는, 이 곱셈의 결과는 장차의 사용을 위해 저장될 수 있다. 1460에서는, 수신된 비-체계적 출력 심볼들을 사용해 벡터 b를 설정한다. L개의 이러한 심볼들이 존재한다면, 벡터 b의 엔트리 수는 L이다. 이 단계는 단지 논리적이기만 할 수 있다. 다시 말해, 이 단계는 어떠한 계산도 필요로 하지 않을 수 있다. 다음으로는, 벡터 y에 저장되어 있는 이전의 곱셈이 벡터 b의 엔트리들과 컴포넌트-방식으로, 즉, 수신된 비-체계적 출력 심볼들 각각이 벡터 y의 대응되는 심볼들과 XOR된 다. 이 연산의 결과는 수신된 비-체계적 심볼들을 대신해 저장되거나 상이한 위치에 저장될 수 있다.

이러한 XOR가 판정되고 나면, 소실된 체계적 심볼들에 대응되는 행렬(H_E)을 사용해 선형 방정식들의 시스템이 설정된다. 다음으로, 시스템 H_E*x=y+b의 해(x)가 소실된 체계적 심볼들의 값들에 대응된다. 이러한 값들은 1470에서 출력된다. 이 프로세스 또한 다양한 방식으로, 예를 들어, 가우스 소거 또는 Luby I, Raptor, 또는 비활성화 디코딩에 개시되어 있는 연쇄 반응 디코딩의 변형들 중 어느 하나를 사용해, 수행될 수 있다.

디코딩의 이러한 행렬 관점은 예시적인 목적을 위한 것일 뿐 한정적인 것은 아니다. 본 개시를 참조하는 당업자들에게는 이러한 디코딩 절차의 많은 변형들이 명백할 것이다.

Ⅲ. 예시적인 체계적 코딩 및 디코딩

이제는, 도 15 내지 도 17을 참조하여, 체계적 연쇄 반응 코딩 시스템의 일부 실시예들의 연산들에 대한 일부 태양들의 간단한 예를 제시할 것이다. 제시된 모든 예들에서, 가중치 도표의 영향은, 소정 심볼의 키가 주어진 상태에서, 소정 심볼의 이웃들에 대한 리스트의 관점에서 암시적으로 서술될 뿐이다.

체계적 키들 계산하기

도 15A는 체계적 키들(C₀, C₁, ..., C₈)을 획득하는데 사용되는 디코딩 그래프를 설명한다. 예를 들어, 도 11의 1110 연산에 의해 이미 12개의 키들(D(0), D(1), ..., D(11))이 생성되었다고 가정한다. 도 15A의 그래프는 키들(D(0), ..., D(11))을 사용하는, 1520(a), ..., 1520(i)로 지시되는 입력 노드들과 1530(a), ..., 1530(l)로 지시되는 출력 노드들간의 변형된 디코딩 그래프를 설명한다. 이제, 연쇄 반응 디코딩 중에 입력 노드의 복구를 트리거하는 출력 노드들의 키들로서 체계적 키들을 획득하기 위해, 이 그래프에 연쇄 반응 디코딩이 적용된다.

연산시에, 노드(1530(a))는 입력 노드(1520(b))를 복구하는데 사용될 수 있다. 따라서, 제 1의 체계적 키(C₀)는 생성된 키들 중 첫번째, 즉, D(0)와 동일하다. 입력 노드(1520(b))의 복구로 인해, 출력 노드(1530(c))가 차수 1이 되고, 따라서 노드(1520(e))의 복구를 트리거한다. 이런 식으로 계속하면, 도 15A의 밝은 회색 노드들이 입력 노드들을 복구하는데 사용될 수 있다는 것을 알 수 있다. 입력 노드들을 복구하는데 사용되는 출력 노드들의 시퀀스는 1530(a), 1530(b), 1530(c), 1530(d), 1530(e), 1530(f), 1530(g), 1530(h), 1530(i)이다. 그 결과, 체계적 키들의 시퀀스는 도 15B에 나타낸 바와 같이 선택될 수 있다.

도시된 연쇄 반응 디코딩을 위한 복구 프로세스는 단지 개념일 뿐이라는 것에 주의해야 한다. 특히, 이러한 특정 예에서는 XOR 연산이 수행되지 않는다.

체계적 인코딩

도 9A에서 약술된 바와 같이, 체계적 연쇄 반응 인코더는 연쇄 반응 디코더(910) 및 연쇄 반응 인코더(920)로 이루어진다. 따라서, 체계적 연쇄 반응 인코딩의 연산은 2개 부분들로 분할된다. 이러한 2개 부분들이 도 16A 및 도 16B에 각각 예시되어 있다.

도 16A는 연쇄 반응 디코더(910)의 연산을 예시한다. 입력 심볼들은 IS(0), ..., IS(8)으로 지시된다. 키들(C₀, C₁, ..., C₈)은 입력 심볼들과 중간 입력 심볼들간에 그래프적인 의존성을 설정하는데 사용된다. 예를 들어, 키(C₀)는, IS(0)가 S(1)의 값과 동일하다는 것을 나타내는 한편, 키 C₄는, IS(4)가 S(2), S(5), 및 S(7)의 값들에 대한 XOR와 동일하다는 것을 나타낸다. 이제, 값들(S(0), S(1), ..., S(8))을 획득하기 위해, 연쇄 반응 디코딩이 적용된다. 이러한 값들을 획득하기 위한 스케줄은, 이 스케줄이 키들(C₀, C₁, ..., C₈)을 획득하기 위해 설정된 것이므로, 도 7C의 체계적 키 생성기(730)로부터 연쇄 반응 디코더(910)로 전달되었을 수도 있다. 체계적 키 생성기의 연산과 달리, 이 단계는 개개 심볼들의 값들에 대한 XOR를 이용할 수 있다.

도 16A의 예에서, 스케줄은 먼저 S(1)의 값을 발생시킬 수 있는데, 이 값은 IS(1)의 값을 사용해 S(4)의 값을 발생시킬 수 있다. 이것은 S(0) 및 S(7) 등의 값들에 대한 복구를 트리거한다.

도 16B는, 우선 11개의 비-체계적 출력 심볼들(O(0), ..., O(10))의 생성을 나타내는 것에 의해, 도 9A의 연쇄 반응 인코더(920) 연산을 예시한다. (도시된 출력 심볼들(O(i))은 이전에 설명된 출력 심볼들(B(I_i))을 의미한다.) 앞서 설명된 바와 같이, 체계적 인코더의 출력은 출력 심볼들(O(0), ..., O(10))이 수반되는 체 계적 출력 심볼들(IS(0), ..., IS(8))로 이루어진다. 이러한 특정 순서화는 단지 예시적인 것이며, 본 발명에 따른 다른 실시예들에서는 다른 순서화가 사용될 수도 있다.

체계적 디코딩

도 17A 및 도 17B는 체계적 연쇄 반응 디코딩 프로세스의 실시예를 예시한다. 수신된 체계적 출력 심볼들은 IS(1), IS(6), 및 IS(7)인 한편, 수신된 비-체계적 출력 심볼들은 O(0), O(3), O(4), O(6), O(7), O(8), O(9), 및 O(10)이라고 가정한다. 디코더의 태스크는 누락된 체계적 출력 심볼들의 값들, 즉, IS(0), IS(2), IS(3), IS(4), IS(5), 및 IS(8)의 값들을 계산하는 것이다. 도 17A는, 도 9B의 연쇄 반응 디코더(930)와 연쇄 반응 인코더(940)가 하나의 디코더로 조합될 수 있는 방법에 대한 일례이다. 일부 애플리케이션들에서는, 이러한 조합이 계산 절감을 초래할 수 있다.

수신된 체계적 출력 심볼들에 대응되는 키들(C₁, C₆, 및 C₇) 및 수신된 비-체계적 출력 심볼들에 대응되는 키들을 사용하여, 수신된 출력 심볼들과 중간 입력 심볼들(S(0), ..., S(8))간의 그래프가 설정된다. 중간 입력 심볼들간의 XOR가 출력 심볼을 산출하는 모든 중간 입력 심볼들과 출력 심볼간에 연결 선이 그려진다. 개개의 접속들은 도 16A 및 도 16B에 나타낸 것들과 동일하다. 수신된 출력 심볼들의 특정한 순서는 디코딩 그래프를 표현하기 위해 선택된 순서와 동일하지 않을 수도 있다.

이 그래프는, 소실된 체계적 출력 심볼들에 대응되는 다른 또 한 층의 노드들에 의해 확장된다. 이 그래프는, 입력 심볼들(IS(0), IS(2), IS(3), IS(4), IS(5), 및 IS(8))이 점선들을 통해 입력 심볼들의 XOR인 중간 입력 심볼들에 접속되어 있는, 도 17A의 상부에 대응된다. 마찬가지로, 도 17A의 대응되는 접속들에 대해 이러한 접속들이 확인될 수 있다.

이러한 특정 예에서의 디코딩 프로세스는, 중간 심볼들 중 하나가 복구될 때마다, 그 값이 도면 상부의 수신되지 않은 원래 심볼들 중에서 이 심볼의 모든 이웃들에 대한 값에 XOR되는, 연쇄 반응 디코딩을 하부 그래프에 적용하는 것에 의해 시작될 수 있다. 원래, 이러한 심볼들의 값들은 0으로 설정될 수 있다.

예를 들어, 출력 심볼(O(4))은 S(3)의 값을 복구하는데 사용될 수 있다. 그 다음, S(3)의 값은 IS(5)의 현재 값으로 XOR될 수 있다. 이러한 단계 이후에, IS(5)의 값은 S(3)의 값과 동일하다. S(3)의 복구는 출력 노드(O(10))의 차수를 1로 감소시킨다. 이 출력 노드는 중간 심볼(S(6))의 값을 복구한다. 이 값은 IS(5)의 현재 값으로 XOR되므로, 이 단계 이후에는 IS(5)의 값이 복구된다. 수신되지 않은 모든 비-체계적 입력 심볼들이 복구될 때까지, 프로세스는 계속된다.

도 17B는, 누락된 출력 심볼들이 복구되는 프로세스를 도시한다. 복구된 심볼들은 직사각형으로 프레임화된다. 복구된 체계적 출력 심볼들은 회색의 직사각형으로 프레임화된다. 이 도면의 에지 레이블들은 복구에 사용된 심볼들을 설명한다.

예를 들어, S(3)의 복구에는 심볼 O(4)가 사용된다. 심볼 O(10)은 S(6)를 복구하는데 사용된다. S(3)과 S(6)는 다같이 S(5)를 복구한다. S(6)의 복구는 (O(9)을 사용해) S(8)의 복구 및 (수신된 체계적 출력 심볼 (IS(7)을 사용해) S(0)의 복구를 트리거한다. S(8)의 복구는 IS(3)의 복구를 트리거한다. S(0)의 복구는 (IS(1)을 사용해) S(4)의 복구를 트리거한다. 한편, O(0)를 사용해, S(8)의 복구는 S(1)의 복구를 트리거하며, S(1)의 복구는 S(4)와 함께 IS(2)를 복구한다. 또한, S(1)의 복구는, 그 값들이 동일하므로, IS(0)의 복구를 초래한다. O(8) 및 S(4)의 복구된 값을 사용하면, S(5)의 값이 획득된다. 이것은, 반대로, IS(8)의 값을 복구하는데, 이것은 후자가 S(5), S(4), 및 S(0)의 XOR이고, 이 값들 모두가 이 단계에서 공지이기 때문이다. IS(6) 및 S(4)를 사용하면, S(7)의 값이 획득된다. O(7)을 사용하면, 이것은, S(7)과 함께, 남아 있는 마지막 입력 심볼, 즉 IS(4)의 값을 복구하는 S(2)의 값을 복구한다.

상기 설명은 예시를 위해 제시되었다. 개시된 정확한 형태로 본 발명을 총망라하거나 한정하려는 것이 아니며, 상기 내용의 관점에서 많은 변형들 및 변경들이 가능하다는 것을 명백히 알 수 있다. 개시된 실시예들은 본 발명의 원리 및 본 발명의 실질적인 애플리케이션을 최선으로 설명함으로써, 당업자들이 본 발명을 다양한 실시예들에서 그리고 상정할 수 있는 특정 용도에 적합한 다양한 변경들로 최선 활용할 수 있도록 하기 위해, 선택되었다. 본 발명의 범위는 여기에 첨부된 청구항들에 의해 정의된다.

참고 문헌들

Michael G. Luby에 의한 (여기에서는 Luby I이라고 하는) "Information Additive Code Generator and Decoder for Communication Systems"라는 명칭의 미국 특허 제 6,307,487호;

"Scheduling of Multiple Files for Serving on a Server"라는 명칭으로 2001년 2월 22일에 출원된 미국 특허출원 제 09/792,364호;

(여기에서는 "Raptor"라고 하는) "Multi-Stage Code Generator and Decoder for Communication Systems"라는 명칭으로 2001년 12월 21일에 출원된 미국 특허출원 제 10/032,156호; 및

(여기에서는 "불활성화 디코딩"이라고 하는) "Systems and Processes for Decoding Chain Reaction Codes through Inactivation"이라는 명칭으로 2003년 6월 10일에 출원된 미국 특허출원 제 10/459,370호

Claims

연쇄 반응 코드에 따라 소스 데이터를 인코딩된 데이터로 인코딩하는 방법으로서, 상기 인코딩된 데이터는 체계적 출력 심볼들 및 비-체계적 출력 심볼들을 가지며, 상기 체계적 출력 심볼들은 소스 데이터 심볼들에 대응하고, 상기 비체계적 출력 심볼들은 하나 이상의 소스 신호들의 함수들에 대응하며, 상기 연쇄 반응 코드는 키 세트로부터의 키들에 따라 입력 심볼들을 출력 심볼들에 맵핑하는 코드인 것인, 상기 인코딩 방법에 있어서,

상기 데이터로부터 입력 심볼들의 세트를 생성하는 단계로서, 상기 입력 심볼들은 체계적 출력 심볼들을 포함하는 것인, 상기 입력 심볼들의 세트를 생성하는 단계; 및

상기 입력 심볼들의 세트로부터 하나 이상의 비-체계적 출력 심볼들을 생성하는 단계로서, 상기 하나 이상의 비-체계적 출력 심볼들 각각은 비-체계적 출력 심볼들의 알파벳으로부터 선택되며, 상기 체계적 출력 심볼들 및 비-체계적 출력 심볼들은 상기 인코딩된 데이터를 형성하는 것인, 상기 하나 이상의 비-체계적 출력 심볼들을 생성하는 단계를 포함하고,

상기 입력 심볼들의 세트에 대한 임의의 서브세트는,

(ⅰ) 사전설정된 갯수의 비-체계적 출력 심볼들, 또는

(ii) (a) 복구될 입력 심볼들의 서브세트에 포함되지 않은, 상기 입력 심볼들의 세트의 입력 심볼들과 (b) 상기 하나 이상의 비-체계적 출력 심볼들과의 조합

으로부터 복구될 수 있는 것인, 인코딩 방법.
제 1 항에 있어서, 상기 하나 이상의 비-체계적 출력 심볼을 생성하는 단계는,

상기 입력 심볼들의 세트로부터, 복수개의 중간 입력 심볼들을 생성하는 단계; 및

상기 복수개의 중간 입력 심볼들을 하나 이상의 비-체계적 출력 심볼들로 인코딩하는 단계로서, 하나 이상의 중간 입력 심볼들이 하나의 비-체계적 출력 심볼로 인코딩되는 것인, 상기 인코딩하는 단계

를 포함하는 것인, 인코딩 방법.
제 2 항에 있어서, 상기 복수개의 중간 입력 심볼들을 생성하는 단계는,

상기 복수개의 입력 심볼들에 대해 체계적 키들을 계산하는 단계; 및

상기 복수개의 입력 심볼들 및 대응하는 체계적 키들로부터, 복수개의 중간 입력 심볼들을 생성하는 단계를 포함하는 것인, 인코딩 방법.
제 3 항에 있어서, 상기 복수개의 입력 심볼들에 대해 체계적 키들을 계산하는 단계는, K개 컬럼들을 가진 행렬을 구성하는 단계를 포함하고, K는 입력 심볼들의 수에 대응하며, 상기 인코딩 방법은,

(ⅰ) 행렬 로우(row) 카운터 J를 0으로 초기화하는 단계;

(ⅱ) J의 함수로서 키(D(J))를 계산하는 단계;

(ⅲ) 상기 행렬의 J번째 로우의 로우 엔트리들을 상기 키(D(J))의 함수로서 계산하는 단계; 및

(ⅳ) 상기 행렬의 로우들이 선형적으로 독립적인지를 판정하는 단계를 포함하고,

상기 행렬의 로우들이 선형적으로 독립적이지 않다면, J는 J+1로 증가되고 상기 (ⅱ) 및 (ⅲ) 단계들이 반복되며, 상기 행렬의 로우들이 선형적으로 독립적이라면, 상기 체계적 키들이 상기 선형적으로 독립적인 로우들의 함수로서 계산되는 것인, 인코딩 방법.
제 4 항에 있어서, 키(D(J))를 계산하는 상기 (ⅱ) 단계는, J의 함수로서 키(D(J))를 계산하기 위해 난수 생성기를 이용하는 단계를 포함하는 것인, 인코딩 방법.
제 4 항에 있어서, 상기 로우 엔트리들은 0 또는 1의 값을 포함하는 것인, 인코딩 방법.
제 3 항에 있어서, 상기 복수개의 입력 심볼들에 대해 체계적 키들을 계산하는 단계는,

(ⅰ) 사전정의된 수 L개의 고유한 키들 D(0)-D(L-1)을 계산하는 단계;

(ⅱ) K개의 컬럼들 및 L개의 로우들을 가진 변형된 디코딩 행렬을 구성하는 단계로서, K는 상기 입력 심볼들의 수에 대응하고, O과 L-1 사이의 임의의 값 j에 대해, j번째 로우를 따르는 로우 엔트리들이 상기 키(D(j))의 함수로서 계산되는 것인, 상기 변형된 디코딩 행렬을 구성하는 단계; 및

(ⅲ) 상기 변형된 디코딩 행렬에 의해 기술되는 선형 방정식들의 세트를 풀어 내는 단계로서, 상기 체계적 키들은 상기 선형 방정식들에 대한 해들(solutions)의 함수로서 계산되는 것인, 상기 선형 방정식들의 세트를 풀어 내는 단계

를 포함하는 것인, 인코딩 방법.
제 1 항에 있어서, 상기 인코딩된 데이터를 통신 채널을 통해 전송하는 단계를 더 포함하는 인코딩 방법.
제 8 항에 있어서,

상기 입력 심볼들의 세트의 제 1 서브세트를 포함하는 하나 이상의 체계적 출력 심볼들을 수신하는 단계;

하나 이상의 비-체계적 출력 심볼들을 수신하는 단계로서, 각각의 비-체계적 출력 심볼은 비체계적 출력 심볼들의 알파벳으로부터 선택되며, 각각의 비-체계적 출력 심볼은 하나 이상의 상기 입력 심볼들의 함수로서 생성되는 것인, 상기 하나 이상의 비-체계적 출력 심볼들을 수신하는 단계; 및

상기 입력 심볼들의 제1 서브 세트에 포함되지 않는 하나 이상의 입력 심볼들을 포함하는 상기 입력 심볼들 세트의 나머지 서브세트를 복구하는 단계를 더 포함하고,

상기 입력 심볼들의 나머지 서브세트는,

(ⅰ) 사정설정된 갯수의 비-체계적 출력 심볼들; 또는

(ⅱ) (a) 상기 제 1 서브세트로부터의 하나 이상의 입력 심볼들과 (b) 하나 이상의 비-체계적 출력 심볼들과의 조합으로부터 복구되는 것인, 인코딩 방법.
제 9 항에 있어서, 상기 입력 심볼들 세트의 나머지 서브세트를 복구하는 단계는,

상기 하나 이상의 수신된 비-체계적 출력 심볼과 상기 하나 이상의 수신된 체계적 입력 심볼과의 조합을 복수개의 중간 입력 심볼들로 디코딩하는 단계; 및

상기 복수개의 중간 입력 심볼들을 상기 입력 심볼들의 나머지 서브세트를 포함하는 복수개의 입력 심볼들로 인코딩하는 단계로서, 상기 입력 심볼들의 나머지 서브세트는 상기 입력 심볼들의 제1 서브 세트에 포함되지 않는 하나 이상의 입력 심볼들을 포함하는 것인, 상기 인코딩하는 단계

를 포함하는 것인, 인코딩 방법.
제10 항에 있어서, 상기 조합을 복수개의 중간 입력 심볼들로 디코딩하는 단계는,

상기 수신된 체계적 출력 심볼들에 대응하는 체계적 키들을 계산하는 단계;

상기 수신된 비-체계적 출력 심볼들에 대응하는 비-체계적 키들을 계산하는 단계; 및

상기 체계적 키들, 상기 비-체계적 키들, 상기 수신된 비-체계적 출력 심볼들, 및 상기 수신된 체계적 출력 심볼들로부터, 상기 복수개의 중간 입력 심볼들을 생성하는 단계를 포함하는 것인, 인코딩 방법.
제10 항에 있어서, 상기 복수개의 중간 입력 심볼들을 상기 입력 심볼들의 나머지 서브세트를 포함하는 하나 이상의 입력 심볼들로 인코딩하는 단계는,

수신되지 않은 상기 체계적 출력 심볼들에 대해 체계적 키들을 계산하는 단계; 및

상기 수신되지 않은 체계적 출력 심볼들에 대응되는 체계적 키들 및 상기 중간 입력 심볼들로부터, 상기 입력 심볼들의 나머지 서브세트를 생성하는 단계를 포함하는 것인, 인코딩 방법.
연쇄 반응 코드에 따라 인코딩된 데이터를 소스 데이터를 나타내는 한 세트의 입력 심볼들로 디코딩하는 방법으로서, 상기 인코딩된 데이터는 체계적 출력 심볼들 및 비-체계적 출력 심볼들을 가지며, 상기 체계적 출력 심볼들은 소스 데이터 심볼들에 대응하고, 상기 비체계적 출력 심볼들은 하나 이상의 소스 신호들의 함수들에 대응하며, 상기 연쇄 반응 코드는 키 세트로부터의 키들에 따라 입력 심볼들을 출력 심볼들에 맵핑하는 코드인 것인, 상기 디코딩 방법에 있어서,

상기 입력 심볼들의 세트의 제1 서브세트를 제공하는 단계로서, 상기 제1 서브세트는 하나 이상의 체계적 출력 심볼을 포함하는 것인, 상기 제1 서브세트를 제공하는 단계;

하나 이상의 비-체계적 출력 심볼들을 제공하는 단계로서, 각각의 비-체계적 출력 심볼은 비-체계적 출력 심볼들의 알파벳으로부터 선택되고, 각각의 비-체계적 추력 심볼은 하나 이상의 상기 입력 심볼들의 함수로서 생성되는 것인, 상기 출력 심볼들을 제공하는 단계; 및

상기 입력 심볼들의 제1 세트에 포함되지 않는 하나 이상의 입력 심볼들을 포함하는 상기 입력 심볼들의 나머지 서브세트를 복구하는 단계

를 포함하고, 상기 입력 심볼들의 나머지 서브세트는,

(ⅰ) 사전설정된 갯수의 비-체계적 출력 심볼들; 또는

(ⅱ) (a) 상기 제 1 서브세트로부터의 하나 이상의 입력 심볼들과 (b) 하나 이상의 비-체계적 출력 심볼들과의 조합으로부터 복구되는 것인, 디코딩 방법.
제 13 항에 있어서, 상기 입력 심볼들의 나머지 서브세트를 복구하는 단계는,

상기 하나 이상의 수신된 비-체계적 출력 심볼과 상기 하나 이상의 수신된 체계적 입력 심볼과의 조합을 복수개의 중간 입력 심볼들로 디코딩하는 단계; 및

상기 복수개의 중간 입력 심볼들을 상기 입력 심볼들의 나머지 서브세트를 포함하는 하나 이상의 입력 심볼로 인코딩하는 단계로서, 상기 입력 심볼들의 제 1 서브세트 및 나머지 서브세트는 집합적으로 상기 입력 심볼들의 세트를 형성하는 것인, 상기 인코딩하는 단계를 포함하는 것인, 디코딩 방법.
제14 항에 있어서, 상기 조합을 복수개의 중간 입력 심볼들로 디코딩하는 단계는,

상기 수신된 체계적 출력 심볼들에 대응하는 체계적 키들을 계산하는 단계;

상기 수신된 비-체계적 출력 심볼들에 대응하는 비-체계적 키들을 계산하는 단계; 및

상기 체계적 키들, 상기 비-체계적 키들, 상기 비-체계적 출력 심볼들, 및 상기 수신된 체계적 출력 심볼들로부터 상기 복수개의 중간 입력 심볼들을 생성하는 단계를 포함하는 것인, 디코딩 방법.
제14 항에 있어서, 상기 복수개의 중간 입력 심볼들을 상기 입력 심볼들의 나머지 서브세트를 포함하는 하나 이상의 입력 심볼로 인코딩하는 단계는,

제공되지 않은 상기 체계적 출력 심볼들에 대해 체계적 키들을 계산하는 단계; 및

수신되지 않은 상기 체계적 출력 심볼들에 대응하는 체계적 키들 및 상기 중간 입력 심볼들로부터, 입력 심볼들의 상기 나머지 서브세트를 생성하는 단계를 포함하는 것인, 디코딩 방법.
제13 항에 있어서, 통신 채널을 따라 송신되는 전송에 의해 상기 인코딩된 데이터를 수신하는 단계를 더 포함하는 디코딩 방법.
연쇄 반응 코드들을 사용해 소스 데이터를 프로세싱하는 방법으로서, 상기 연쇄 반응 코드는 키 세트로부터의 키들에 따라 입력 심볼들을 출력 심볼들에 맵핑하는 코드인 것인, 상기 프로세싱 방법에 있어서,

상기 소스 데이터로부터 입력 심볼들의 세트를 생성하는 단계;

상기 입력 심볼들의 세트로부터 하나 이상의 비-체계적 출력 심볼을 생성하는 단계로서, 상기 하나 이상의 비-체계적 출력 심볼들 각각은 비-체계적 출력 심볼들의 알파벳으로부터 선택되며, 각각의 비-체계적 출력 심볼은 하나 이상의 상기 입력 심볼들의 함수로서 생성된 심볼인 것인, 상기 입력 심볼들의 세트로부터 하나 이상의 비-체계적 출력 심볼을 생성하는 단계;

상기 입력 심볼들의 세트의 제1 서브세트를 수신하는 단계로서, 상기 제1 서브세트의 입력 심볼들은 하나 이상의 체계적 출력 심볼들을 포함하고, 체계적 심볼은, 체계적 심볼이 입력 심볼에 대응한다는 점에서 체계적인 것인, 상기 입력 심볼들의 제1 서브세트를 수신하는 단계;

하나 이상의 비-체계적 출력 심볼을 수신하는 단계; 및

상기 입력 심볼들의 제1 세트에 포함되지 않는 하나 이상의 입력 심볼을 포함하는 상기 입력 심볼들의 나머지 서브세트를 복구하는 단계

를 포함하고, 상기 입력 심볼들의 나머지 서브세트는,

(ⅰ) 사전설정된 갯수의 비-체계적 출력 심볼들; 또는

(ⅱ) (a) 상기 제 1 서브세트로부터의 하나 이상의 입력 심볼들과 (b) 하나 이상의 비-체계적 출력 심볼과의 조합으로부터 복구되는 것인, 프로세싱 방법.
제18 항에 있어서, 상기 하나 이상의 비-체계적 출력 심볼들을 생성하는 단계는,

상기 입력 심볼들의 세트로부터, 복수개의 중간 입력 심볼들을 생성하는 단계; 및

상기 복수개의 중간 입력 심볼들을 하나 이상의 비-체계적 출력 심볼들로 인코딩하는 단계로서, 하나 이상의 중간 입력 심볼들이 하나의 비-체계적 출력 심볼로 인코딩되는 것인, 상기 인코딩하는 단계를 포함하는 것인, 프로세싱 방법.
제19 항에 있어서, 상기 복수개의 중간 입력 심볼들을 생성하는 단계는,

상기 복수개의 입력 심볼들에 대해 체계적 키들을 계산하는 단계; 및

상기 복수개의 입력 심볼들 및 대응하는 체계적 키들로부터, 복수개의 중간 입력 심볼들을 생성하는 단계를 포함하는 것인, 프로세싱 방법.
제18 항에 있어서, 상기 입력 심볼들의 나머지 서브세트를 복구하는 단계는,

상기 하나 이상의 수신된 비-체계적 출력 심볼과 상기 하나 이상의 수신된 체계적 출력 심볼의 조합을 복수개의 중간 입력 심볼들로 디코딩하는 단계; 및

상기 복수개의 중간 입력 심볼들을 상기 입력 심볼들의 나머지 서브세트를 포함하는 하나 이상의 입력 심볼들로 인코딩하는 단계로서, 상기 입력 심볼들의 제 1 서브세트 및 나머지 서브세트는 집합적으로 상기 입력 심볼들의 세트를 형성하는 것인, 상기 인코딩하는 단계를 포함하는 것인, 프로세싱 방법.
제21 항에 있어서, 상기 조합을 복수개의 중간 입력 심볼들로 디코딩하는 단계는,

상기 수신된 체계적 출력 심볼들에 대응하는 체계적 키들을 계산하는 단계;

상기 수신된 비-체계적 출력 심볼들에 대응하는 비-체계적 키들을 계산하는 단계; 및

상기 체계적 키들, 상기 비-체계적 키들, 상기 비-체계적 출력 심볼들, 및 상기 수신된 체계적 출력 심볼들로부터 상기 복수개의 중간 입력 심볼들을 생성하는 단계를 포함하는 것인, 프로세싱 방법.
제21 항에 있어서, 상기 복수개의 중간 입력 심볼들을 상기 입력 심볼들의 나머지 서브세트를 포함하는 하나 이상의 입력 심볼들로 인코딩하는 단계는,

제공되지 않은 체계적 출력 심볼들에 대해 체계적 키들을 계산하는 단계; 및

상기 제공되지 않은 체계적 출력 심볼들에 대응되는 체계적 키들 및 상기 중간 입력 심볼들로부터, 상기 입력 심볼들의 나머지 서브세트를 생성하는 단계를 포함하는 것인, 프로세싱 방법.
제18 항에 있어서, 통신 채널을 따라 송신되는 전송에 의해 상기 체계적 및 비-체계적 출력 심볼들을 수신하는 단계를 더 포함하는 프로세싱 방법.
제18 항에 있어서, 상기 입력 심볼들의 세트의 제1 서브세트를 수신하는 단계는, 상기 입력 심볼들의 세트의 제 1 서브세트를 포함하는 전송을 수신하는 단계를 포함하고,

상기 하나 이상의 비-체계적 출력 심볼들을 수신하는 단계는, 상기 하나 이상의 비-체계적 출력 심볼들을 포함하는 전송을 수신하는 단계를 포함하는 것인, 프로세싱 방법.
연쇄 반응 코드에 따라 한 세트의 입력 데이터를 인코딩된 데이터로 인코딩하도록 구성된 인코더로서, 상기 연쇄 반응 코드는 키 세트로부터의 키들에 따라 입력 심볼들을 출력 심볼들에 맵핑하는 코드이고, 상기 인코딩된 데이터는 체계적 출력 심볼들 및 비-체계적 출력 심볼들을 포함하며, 상기 체계적 출력 심볼들은 소스 데이터 심볼들에 대응하고, 상기 비체계적 출력 심볼들은 하나 이상의 소스 신호들의 함수들에 대응하는 것인, 상기 인코더에 있어서,

상기 입력 데이터 세트를 수신하도록 결합되어 있고, 이에 응답하여 하나 이상의 입력 심볼을 출력하도록 동작할 수 있는, 입력 심볼 생성기;

각각의 입력 심볼에 대응하는 체계적 키를 생성하도록 동작할 수 있는 체계적 키 생성기로서, 상기 체계적 키는 체계적 출력 심볼로서의 출력 심볼을 생성하기 위해 사용되는 키인 것인, 상기 체계적 키 생성기;

하나 이상의 비-체계적 키들을 생성하도록 동작할 수 있는 비-체계적 키 생성기; 및

상기 하나 이상의 입력 심볼들, 상기 체계적 키들, 및 상기 비-체계적 키들을 수신하고, 이에 응답하여 하나 이상의 비-체계적 키들 및 하나 이상의 입력 심볼들을 출력하도록 결합되어 있는 체계적 인코더로서, 상기 인코딩된 심볼들은 적어도 하나의 체계적 출력 심볼을 포함하는 것인, 상기 체계적 인코더

를 포함하는 인코더.
제26 항에 있어서, 상기 체계적 인코더는,

상기 하나 이상의 입력 심볼들 및 상기 하나 이상의 입력 심볼들에 대응되는 체계적 키들을 수신하도록 결합되어 있으며, 응답하여 하나 이상의 중간 입력 심볼들을 발생시키도록 동작할 수 있는 연쇄 반응 디코더; 및

상기 하나 이상의 중간 입력 심볼들 및 상기 하나 이상의 비-체계적 키들을 수신하도록 결합되어 있으며, 응답하여 하나 이상의 비-체계적 출력 심볼들을 발생시키도록 동작할 수 있는 연쇄 반응 인코더

를 포함하는 것인, 인코더.
제27 항에 있어서, 상기 하나 이상의 입력 심볼들 및 상기 하나 이상의 비-체계적 출력 심볼들을 수신하도록 결합된 전송 모듈을 더 포함하고, 상기 전송 모듈은 상기 입력 심볼들 및 상기 비-체계적 출력 심볼들을 전송하도록 동작할 수 있으며, 상기 전송된 입력 심볼들은 체계적 출력 심볼들을 포함하는 것인, 인코더.
연쇄 반응 코드에 따라 인코딩된 데이터를 디코딩하도록 구성된 디코더로서, 상기 인코딩된 데이터는 비-체계적 출력 심볼들 및 체계적 출력 심볼들을 포함하며, 상기 체계적 출력 심볼들은 소스 데이터 심볼들에 대응하고, 상기 비체계적 출력 심볼들은 하나 이상의 소스 신호들의 함수들에 대응하며, 상기 연쇄 반응 코드는 키 세트로부터의 키들에 따라 입력 심볼들을 출력 심볼들에 맵핑하는 코드인 것인, 상기 디코더에 있어서,

각각의 획득된 비-체계적 출력 심볼들에 대해 비-체계적 키들의 세트를 생성하도록 구성되어 있는 비-체계적 키 생성기로서, 상기 비-체계적 키는 비-체계적 출력 심볼로서의 출력 심볼을 생성하기 위해 사용되는 키인 것인, 상기 비-체계적 키 생성기;

하나 이상의 체계적 키들을 재생하도록 구성되어 있는 체계적 키 생성기로서, 상기 체계적 키는 체계적 출력 심볼로서의 출력 심볼을 생성하기 위해 사용되는 키인 것인, 상기 체계적 키 생성기; 및

상기 하나 이상의 체계적 출력 심볼들, 상기 하나 이상의 체계적 출력 심볼들, 상기 체계적 키들, 및 상기 비-체계적 키들을 수신하고, 응답하여, 상기 인코딩된 데이터로서 인코딩되었던 소스 데이터에 대응하는 하나 이상의 입력 심볼들을 출력하도록 결합된 체계적 디코더

를 포함하는 디코더.
제29 항에 있어서, 상기 체계적 키 재생기는 체계적 키들의 제1 세트 및 체계적 키들의 제2 세트를 재생하도록 구성되어 있고, 상기 체계적 키들의 제 1 세트의 각각은 획득된 체계적 출력 심볼에 대응하고, 상기 체계적 키들의 제 2 세트의 각각은 누락된 체계적 출력 심볼에 대응하도록 되어 있는 것인, 디코더.
제30 항에 있어서, 상기 체계적 디코더는,

상기 수신된 체계적 출력 심볼들, 상기 비-체계적 키들의 세트, 및 상기 체계적 키들의 제 1 및 제 2 세트를 수신하도록 결합되어 있고, 응답하여 중간 입력 심볼들의 대응하는 세트를 발생시키는 연쇄 반응 디코더; 및

상기 중간 입력 심볼들 및 상기 체계적 키들의 제2 세트를 수신하도록 결합되어 있으며, 응답하여 상기 누락된 체계적 출력 심볼들의 사본을 발생시키는 연쇄 반응 인코더를 포함하고,

상기 누락된 체계적 출력 심볼들의 사본과 조합한 상기 수신된 체계적 출력 심볼들은, 상기 소스 데이터에 대응하는 전송된 입력 심볼들의 완전한 세트를 포함하는 것인, 디코더.
데이터를 연쇄 반응 코드로 인코딩하기 위한 컴퓨터 판독가능 매체로서, 상기 연쇄 반응 코드는 키 세트로부터의 키들에 따라 입력 심볼들을 출력 심볼들에 맵핑하는 코드이고, 상기 연쇄 반응 코드는 체계적 출력 심볼들 및 비-체계적 출력 심볼들을 포함하고, 상기 체계적 출력 심볼들은 소스 데이터 심볼들에 대응하고, 상기 비체계적 출력 심볼들은 하나 이상의 소스 신호들의 함수들에 대응하는 것인, 상기 컴퓨터 판독가능 매체에 있어서,

상기 데이터로부터 입력 심볼들의 세트를 생성하기 위한 컴퓨터 판독가능한 프로그램 수단으로서, 상기 입력 심볼들은 체계적 출력 심볼들을 포함하는 것인, 상기 컴퓨터 판독가능한 프로그램 수단; 및

상기 입력 심볼들의 세트로부터 하나 이상의 비-체계적 출력 심볼들을 생성하기 위한 컴퓨터 판독가능한 프로그램 수단으로서, 상기 하나 이상의 비-체계적 출력 심볼들 각각은 비-체계적 출력 심볼들의 알파벳으로부터 선택되며, 각각의 비-체계적 출력 심볼은 하나 이상의 상기 입력 심볼들의 함수로서 생성되며, 상기 체계적 출력 심볼과 상기 비-체계적 출력 심볼은 상기 인코딩된 데이터를 형성하는 것인, 상기 컴퓨터 판독가능한 프로그램 수단

을 포함하고,

상기 입력 심볼들의 세트에 대한 임의의 서브세트는,

(ⅰ) 사전설정된 갯수의 비-체계적 출력 심볼들, 또는

(ⅱ) (a) 복구될 입력 심볼들의 서브세트에 포함되지 않은, 상기 입력 심볼들의 세트의 입력 심볼들과 (b) 상기 하나 이상의 비-체계적 출력 심볼들과의 조합으로부터 복구될 수 있는 것인, 컴퓨터 판독가능 매체.
제32 항에 있어서, 상기 하나 이상의 비-체계적 출력 심볼들을 생성하기 위한 컴퓨터 판독가능한 프로그램 수단은,

상기 입력 심볼들의 세트로부터 복수개의 중간 입력 심볼들을 생성하기 위한 컴퓨터 판독가능한 프로그램 수단; 및

상기 복수개의 중간 입력 심볼들을 하나 이상의 비-체계적 출력 심볼들로 인코딩하기 위한 컴퓨터 판독가능한 프로그램 수단으로서, 하나 이상의 중간 입력 심볼들은 하나의 비-체계적 출력 심볼로 인코딩되는 것인, 상기 컴퓨터 판독가능한 프로그램 수단

을 포함하는 것인, 컴퓨터 판독가능 매체.
제33 항에 있어서, 상기 복수개의 중간 입력 심볼들을 생성하기 위한 컴퓨터 판독가능한 프로그램 수단은,

상기 복수개의 입력 심볼들에 대해 체계적 키들을 계산하기 위한 컴퓨터 판독가능한 프로그램 수단; 및

상기 복수개의 입력 심볼들 및 대응하는 체계적 키들로부터, 복수개의 중간 입력 심볼들을 생성하기 위한 컴퓨터 판독가능한 프로그램 수단

을 포함하는 것인, 컴퓨터 판독가능 매체.
연쇄 반응 코드를 한 세트의 입력 심볼들로 디코딩하기 위한 컴퓨터 판독가능 매체로서, 상기 연쇄 반응 코드는 키 세트로부터의 키들에 따라 입력 심볼들을 출력 심볼들에 맵핑하는 코드이고, 상기 연쇄 반응 코드는 체계적 출력 심볼들 및 비-체계적 출력 심볼들을 포함하며, 상기 체계적 출력 심볼들은 소스 데이터 심볼들에 대응하고, 상기 비체계적 출력 심볼들은 하나 이상의 소스 신호들의 함수들에 대응하는 것인, 상기 컴퓨터 판독가능 매체에 있어서,

상기 입력 심볼들의 세트의 제 1 서브세트를 제공하기 위한 컴퓨터 판독가능한 프로그램 수단으로서, 상기 제1 서브세트는 하나 이상의 체계적 출력 심볼을 포함하는 것인, 상기 컴퓨터 판독가능한 프로그램 수단;

하나 이상의 비-체계적 출력 심볼들을 제공하기 위한 컴퓨터 판독가능한 프로그램 수단으로서, 각각의 비-체계적 출력 심볼은, 비-체계적 출력 심볼들의 알파벳으로부터 선택되며, 하나 이상의 상기 입력 심볼들의 함수로서 생성되는 것인, 상기 컴퓨터 판독가능한 프로그램 수단; 및

상기 입력 심볼들의 제1 세트에 포함되지 않은 하나 이상의 입력 심볼들을 포함하는 상기 입력 심볼들의 나머지 서브세트를 복구하기 위한 컴퓨터 판독가능한 프로그램 수단

을 포함하고, 상기 입력 심볼들의 나머지 서브세트는,

(ⅰ) 사전설정된 갯수의 비-체계적 출력 심볼들; 또는

(ⅱ) (a) 상기 제 1 서브세트로부터의 하나 이상의 입력 심볼들과 (b) 하나 이상의 비-체계적 출력 심볼과의 조합으로부터 복구되는 것인, 컴퓨터 판독가능 매체.
제35 항에 있어서, 상기 입력 심볼들의 나머지 서브세트를 복구하기 위한 컴퓨터 판독가능한 프로그램 수단은,

상기 하나 이상의 수신된 비-체계적 출력 심볼들과 상기 하나 이상의 수신된 체계적 입력 심볼들과의 조합을 복수개의 중간 입력 심볼들로 디코딩하기 위한 컴퓨터 판독가능한 프로그램 수단; 및

상기 복수개의 중간 입력 심볼들을, 상기 입력 심볼들의 나머지 서브세트를 포함하는 하나 이상의 입력 심볼들로 인코딩하기 위한 컴퓨터 판독가능한 프로그램 수단으로서, 상기 입력 심볼들의 제 1 서브세트 및 나머지 서브세트는 집합적으로 상기 입력 심볼들의 세트를 형성하는 것인, 상기 컴퓨터 판독가능한 프로그램 수단

을 포함하는 것인, 컴퓨터 판독가능 매체.
제36 항에 있어서, 상기 조합을 디코딩하기 위한 컴퓨터 판독가능한 프로그램 수단은,

상기 수신된 체계적 출력 심볼들에 대응하는 체계적 키들을 계산하기 위한 컴퓨터 판독가능한 프로그램 수단으로서, 상기 체계적 키는 체계적 출력 심볼로서의 출력 심볼을 생성하기 위해 사용되는 키인 것인, 상기 컴퓨터 판독가능한 프로그램 수단;

상기 수신된 비-체계적 출력 심볼들에 대응하는 비-체계적 키들을 계산하기 위한 컴퓨터 판독가능한 프로그램 수단으로서, 상기 비-체계적 키는 비-체계적 출력 심볼로서의 출력 심볼을 생성하기 위해 사용되는 키인 것인, 상기 컴퓨터 판독가능한 프로그램 수단; 및

상기 체계적 키들, 상기 비-체계적 키들, 상기 비-체계적 출력 심볼들, 및 상기 수신된 체계적 출력 심볼들로부터 상기 복수개의 중간 입력 심볼들을 생성하기 위한 컴퓨터 판독가능한 프로그램 수단

을 포함하는 것인, 컴퓨터 판독가능 매체.
제36 항에 있어서, 상기 복수개의 중간 입력 심볼들을 상기 입력 심볼들의 나머지 서브세트를 포함하는 하나 이상의 입력 심볼들로 인코딩하기 위한 컴퓨터 판독가능한 프로그램 수단은,

제공되지 않은 체계적 출력 심볼들에 대해 체계적 키들을 계산하기 위한 컴퓨터 판독가능한 프로그램 수단으로서, 상기 체계적 키는 체계적 출력 심볼로서의 출력 심볼을 생성하기 위해 사용되는 키인 것인, 상기 컴퓨터 판독가능한 프로그램 수단; 및

상기 제공되지 않은 체계적 출력 심볼들에 대응하는 체계적 키들 및 상기 중간 입력 심볼들로부터, 상기 입력 심볼들의 나머지 서브세트를 생성하기 위한 컴퓨터 판독가능한 프로그램 수단

을 포함하는 것인, 컴퓨터 판독가능 매체.