[go: up one dir, main page]

JP4798164B2 - 送信装置および方法、受信装置および方法、並びにプログラム - Google Patents

送信装置および方法、受信装置および方法、並びにプログラム Download PDF

Info

Publication number
JP4798164B2
JP4798164B2 JP2008096273A JP2008096273A JP4798164B2 JP 4798164 B2 JP4798164 B2 JP 4798164B2 JP 2008096273 A JP2008096273 A JP 2008096273A JP 2008096273 A JP2008096273 A JP 2008096273A JP 4798164 B2 JP4798164 B2 JP 4798164B2
Authority
JP
Japan
Prior art keywords
data
generator polynomial
crc
generator
code length
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
JP2008096273A
Other languages
English (en)
Other versions
JP2009253440A (ja
Inventor
仁 品川
誠 野田
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Sony Corp
Original Assignee
Sony Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Sony Corp filed Critical Sony Corp
Priority to JP2008096273A priority Critical patent/JP4798164B2/ja
Priority to EP09727863.4A priority patent/EP2264905A4/en
Priority to PCT/JP2009/056881 priority patent/WO2009123280A1/ja
Priority to US12/934,159 priority patent/US9209931B2/en
Priority to CN2009801121320A priority patent/CN101983481B/zh
Publication of JP2009253440A publication Critical patent/JP2009253440A/ja
Application granted granted Critical
Publication of JP4798164B2 publication Critical patent/JP4798164B2/ja
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/0001—Systems modifying transmission characteristics according to link quality, e.g. power backoff
    • H04L1/0009—Systems modifying transmission characteristics according to link quality, e.g. power backoff by adapting the channel coding
    • H04L1/001—Systems modifying transmission characteristics according to link quality, e.g. power backoff by adapting the channel coding applied to control information
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0056—Systems characterized by the type of code used
    • H04L1/007—Unequal error protection
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/09—Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/35—Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0072—Error control for data other than payload data, e.g. control data

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Theoretical Computer Science (AREA)
  • Quality & Reliability (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Prevention Of Errors In Transmission (AREA)

Description

本発明は、送信装置および方法、受信装置および方法、並びにプログラムに関し、特に、符号長の異なる複数のデータに対してCRCを用いるシステムにおいて限界値に近い未検出誤り確率特性が得られるようにした送信装置および方法、受信装置および方法、並びにプログラムに関する。
情報記録装置から情報再生装置に対してデータを伝送する場合、または、送信装置から受信装置に対してデータを送信する場合、伝送路上などにおいてデータに誤りが生じることがある。データに誤りが生じたかどうかを検出する方法としてCRC(Cyclic Redundancy Check)（巡回冗長検査）がある。CRCを行うためには、送信対象のデータを送信側の装置において予めCRC符号化しておく必要がある。
図１は、送受信システムの構成例を示すブロック図である。
図１の送受信システムは、送信装置１と受信装置３が伝送路２を介して接続されることによって構成される。送信装置１はCRC符号器１１、誤り訂正符号器１２、および伝送路符号器１３から構成され、受信装置３は符号検出器２１、伝送路復号器２２、誤り訂正復号器２３、およびCRC検出器２４から構成される。送信対象のデータである送信データは、CRC符号化処理の対象の情報語として送信装置１のCRC符号器１１に入力される。
CRC符号化処理の対象となる情報語は１，０の値をとるビット列の形でCRC符号器１１に入力されるため、以下、適宜、CRC符号化処理の対象となる情報語を情報ビット系列ともいう。また、情報ビット系列にCRC符号化処理を施すことによって得られる、１，０の値をとるビット列で表される符号語（CRC符号）を符号ビット系列という。
CRC符号器１１は、入力された情報語にCRCパリティを付加することによってCRC符号化処理を行う。CRC符号器１１は、CRC符号化処理を行うことによって得られたCRC符号を誤り訂正符号器１２に出力する。
誤り訂正符号器１２は、CRC符号器１１から供給されたCRC符号に対してReed-Solomon符号化処理などの誤り訂正符号化処理を施し、誤り訂正符号化処理を施すことによって得られたデータを伝送路符号器１３に出力する。
伝送路符号器１３は、誤り訂正符号器１２から供給されたデータに対して、伝送路２に応じた符号化処理（変調処理等）を施し、得られたデータを伝送路２を介して受信装置３に送信する。伝送路符号器１３から送信されたデータを表す信号は伝送路２を介して受信装置３の符号検出器２１に入力される。
符号検出器２１は、入力された信号に基づいてデータを検出し、検出したデータを伝送路復号器２２に出力する。
伝送路復号器２２は、符号検出器２１から供給されたデータに対して伝送路２に応じた復号処理（復調処理等）を施し、得られたデータを誤り訂正復号器２３に出力する。
誤り訂正復号器２３は、伝送路復号器２２から供給されたデータに対して誤り訂正処理を施し、誤り訂正処理を施すことによって得られたデータを受信データとして出力する。誤り訂正復号器２３から出力された受信データは、１，０の値をとるビット列からなる受信ビット系列として後段の装置に供給されるとともに、CRC検出器２４に供給される。
CRC検出器２４は、誤り訂正復号器２３から供給された受信ビット系列に対してCRC処理を施し、誤り訂正が正しく行われたかどうか、すなわち、受信ビット系列に誤りがあるかどうかを判定する。CRC検出器２４は、判定結果を表す一致信号を後段の装置に出力する。
受信装置３の後段にある装置が記録装置であり、その記録装置に、受信データを記録媒体に記録させるドライブが設けられている場合、CRC検出器２４から出力された一致信号は、ドライブのコントローラにおいてデータの再送信要求を送信装置１に対して行うか否かを判断するためなどの信頼性向上のために用いられる。CRC符号のその他の用途として、符号検出器２１におけるポストプロセッサの一部として用いられたり、ヘッダ情報や、パケット通信における送信パケットに対しても用いられたりする。
ここで、CRC符号による誤り検出の原理について説明する。
ｋビットからなる情報語にｒビットのパリティを付加して符号長ｎ（ｎ＝ｋ＋ｒ）ビットの符号語とする場合、情報語を多項式で表現した（k-1）次（order)の情報多項式M(x)にｘrを掛けた値M(x)・ｘrは、その値をｒ次の生成多項式（generator polynomial）G(x)で割ったときに得られる（r-1）次の剰余多項式をR(x)、商多項式をQ(x)とすると下式（１）によって表される。また、CRC符号化処理によって得られた符号語を（n-1）次の符号多項式W(x)とすると、符号多項式W(x)は下式（２）によって表される。
Figure 0004798164
Figure 0004798164
式（１）、（２）から、符号多項式W(x)は下式（３）で表される。この符号多項式W(x)は生成多項式G(x)で割り切れる式となる。
Figure 0004798164
以上のことから、図１の送信装置１から送信された、符号多項式W(x)で表される符号語を受信した受信装置３のCRC検出器２４においては、誤り訂正復号器２３から供給された受信データを受信多項式Y(x)とすると、この受信多項式Y(x)が生成多項式G(x)で割り切れるかどうかが調べられる。
その結果、受信多項式Y(x)が生成多項式G(x)で割り切れる場合、受信多項式Y(x)は符号多項式W(x)と一致していることになるので、CRC検出器２４においては誤りが発生しなかったと判定される。一方、受信多項式Y(x)が生成多項式G(x)で割り切れない場合、受信多項式Y(x)が符号多項式W(x)と一致していないことになるので、CRC検出器２４においては伝送路２上で誤りが生じたと判定される。
CRC符号は巡回符号であるため、生成多項式G(x)が定まればシフトレジスタと排他的論理和演算回路を用いて容易に装置化することが可能である。生成多項式G(x)としては、１６ビットCRCであるCRC-CCITT（G(x)＝x16＋x12＋x5＋１）やCRC-ANSI（G(x)＝x16＋x15＋x2＋１）が広く知られている。
以下、生成多項式G(x)＝x3＋x＋１（ｒ＝３）とした場合の送信装置１のCRC符号器１１と受信装置３のCRC検出器２４の構成について説明する。
図２は、CRC符号器１１の構成例を示す図である。
図２に示されるように、CRC符号器１１は、CRCパリティ生成器３１、セレクタ３２、セレクタ３３、およびビット数カウンタ３４から構成される。このような構成を有するCRC符号器１１においては、情報多項式M(x)で表される情報ビット系列から符号多項式W(x)で表される符号ビット系列が生成される。
CRCパリティ生成器３１は、ｋビットの情報ビット系列に付加するｒビットのCRCパリティを生成し、生成したCRCパリティをセレクタ３２に出力する。CRCパリティ生成器３１の構成については図３を参照して後述する。
セレクタ３２は、図示せぬ制御回路から出力されるセレクト信号Ｓ０に従って、CRCパリティ生成器３１から入力端子００，０１，１０に入力された出力Ｒ００out，Ｒ０１out，Ｒ０２outのうちの１つを順に選択し、セレクタ３３の「１」入力端子に出力する。
セレクタ３３は、ビット数カウンタ３４から出力されるセレクト信号Ｓ１に従って、「０」入力端子にｋビットの情報ビット系列が入力される期間においてはその情報ビット系列を選択してそのまま出力する。また、セレクタ３３は、情報ビット系列の入力が終わったタイミングで、「１」入力端子に入力されたセレクタ３２の出力であるCRCパリティを選択して出力する。
このように、セレクタ３３からは、ｋビットの情報ビット系列と、ｋビットの情報ビット系列に基づいて生成されたｒビットのCRCパリティからなる、符号長ｎ＝ｋ＋ｒの符号ビット系列が出力される。
図３は、図２のCRCパリティ生成器３１の構成例を示す回路図である。上述したように、生成多項式G(x)はx3＋x＋１である。
図３に示されるように、CRCパリティ生成器３１は、シフトレジスタＲ００、第１の排他的論理和演算回路であるEXOR１、シフトレジスタＲ０１、シフトレジスタＲ０２、および、第２の排他的論理和演算回路であるEXOR２が巡回状に接続されることによって構成される。EXOR２の出力はシフトレジスタＲ００に入力されるとともにEXOR１に入力される。
情報多項式M(x)によって表される情報ビット系列は、毎時刻（例えば、シフトレジスタを動作させるクロック信号で規定される１タイミング毎に）、高次の項のビットから順に１ビットずつEXOR２に入力される。情報多項式M(x)にｘrが予め乗じられた形の情報ビット系列M(x)・ｘrがCRCパリティ生成器３１に入力されることになる。シフトレジスタＲ００，Ｒ０１，Ｒ０２の初期値は０である。
情報ビット系列の零次の項のビットをCRCパリティ生成器３１に入力し終えたとき、図示せぬ制御回路から出力されるイネーブル信号Ｅ０がディセーブル（不活性状態）となり、シフトレジスタＲ００，Ｒ０１，Ｒ０２の値は保持される。この、情報ビット系列の零次の項のビットをCRCパリティ生成器３１に入力し終えた時点でのシフトレジスタＲ００，Ｒ０１，Ｒ０２の値が、剰余多項式R(x)の各次数の係数となる。すなわち、剰余多項式R(x)は、R(x)＝（Ｒ０２の値）×ｘ2＋（Ｒ０１の値）×ｘ＋（Ｒ００の値）で表される。
シフトレジスタＲ００，Ｒ０１，Ｒ０２の値は、それぞれ、出力Ｒ００out，Ｒ０１out，Ｒ０２outとしてセレクタ３２に出力される。出力Ｒ００outはセレクタ３２の入力端子００に入力され、出力Ｒ０１outは入力端子０１に入力され、出力Ｒ０２outは入力端子００に入力される。
図４は、受信装置３のCRC検出器２４の構成例を示す図である。
図４に示されるように、CRC検出器２４はCRCパリティ検査器４１と比較器４２から構成される。このような構成を有するCRC検出器２４において、誤り訂正復号器２３から供給された受信多項式Y(x)で表される受信ビット系列に誤りがないかどうかの検査が行われる。
CRCパリティ検査器４１は、受信多項式Y(x)を生成多項式G(x)で割り、剰余多項式R(x)の係数を表す出力Ｒ１０out，Ｒ１１out，Ｒ１２outを比較器４２に出力する。
比較器４２は、CRCパリティ検査器４１からの出力Ｒ１０out，Ｒ１１out，Ｒ１２outに基づいて、受信多項式Y(x)を生成多項式G(x)で割った結果に剰余があるか否かを判断する。
比較器４２は、出力Ｒ１０out，Ｒ１１out，Ｒ１２outの値が全て０であることから、受信多項式Y(x)を生成多項式G(x)で割った結果に剰余がなく、受信多項式Y(x)が生成多項式G(x)で割り切れたと判断した場合、受信多項式Y(x)は符号多項式W(x)と一致することからデータに誤りが発生していないと判定し、そのことを表す一致信号を出力する。また、比較器４２は、受信多項式Y(x)を生成多項式G(x)で割った結果に剰余があり、受信多項式Y(x)が生成多項式G(x)で割り切れなかったと判断した場合、受信多項式Y(x)は符号多項式W(x)と一致していないことからデータに誤りが発生したと判定し、そのことを表す一致信号を出力する。
図５は、図４のCRCパリティ検査器４１の構成例を示す回路図である。
CRCパリティ検査器４１の構成は図３に示されるCRCパリティ生成器３１の構成に対応しており、図５に示されるように、第１の排他的論理和演算回路であるEXOR１１、シフトレジスタＲ１０、第２の排他的論理和演算回路であるEXOR１２、シフトレジスタＲ１１、およびシフトレジスタＲ１２が巡回状に接続されることによって構成される。シフトレジスタＲ１２の出力は出力Ｒ１２outとして比較器４２に入力されるとともに、EXOR１１とEXOR１２に入力される。
受信多項式Y(x)によって表される受信ビット系列は、毎時刻、高次の項のビットから順に１ビットずつEXOR１１に入力される。シフトレジスタＲ１０，Ｒ１１，Ｒ１２の初期値は０である。
受信ビット系列の零次の項のビットをCRCパリティ検査器４１に入力し終えた時点でのシフトレジスタＲ１０，Ｒ１１，Ｒ１２の値が、剰余多項式R(x)の各次数の係数となる。すなわち、剰余多項式R(x)は、R(X)＝（Ｒ１２の値）×ｘ2＋（Ｒ１１の値）×ｘ＋（Ｒ１０の値）で表される。
シフトレジスタＲ１０，Ｒ１１，Ｒ１２の値は、それぞれ、出力Ｒ１０out，Ｒ１１out，Ｒ１２outとして比較器４２に出力される。
以上のような構成を有する装置によって実現されるCRCの性能は、一般的に、生成多項式G(x)の次数、未検出誤り確率Ｐud、および、最小ハミング距離dminによって大きく影響を受ける。
例えば、ランダム誤り検出能力は、（dmin−１）個以下の全ての誤りを検出できるものとなる。ただし、それ以外の誤りも数多く検出できる。また、バースト誤り検出能力は、長さが生成多項式Ｇ（ｘ）の次数以下の誤りは全て検出できるものとなる。ただし、長さが生成多項式の次数よりも大きいバースト誤りであっても、その多くは検出可能である。
ここで、未検出誤り確率Ｐudとは、伝送路上で生じた誤りによって、受信ビット系列が、送信された符号ビット系列とは別の符号ビット系列（送信対象のデータとして与えられた情報ビット系列とは別の情報ビット系列に対してCRCパリティを付加して得られた符号ビット系列）に変化してしまい、実際には受信ビット系列に誤りがあるのに、誤りなしとして受信側の装置において判定されてしまう確率をいう。
未検出誤り確率Ｐudは、パリティ数ｒ、符号長ｎ、生成多項式G(x)と符号長ｎが決まると求まる重み分布Ａ、もしくは双対符号（dual code）の重み分布Ｂ、２元対称通信路（Binary Symmetric Channel）におけるチャネルビット誤り確率（遷移確率）εによって下式（４）、（５）のように表される（非特許文献１）。
Figure 0004798164
Figure 0004798164
非特許文献２〜８においては、生成多項式の次数（パリティ数）や符号長に応じた、未検出誤り確率を最小化する様々な生成多項式が提案されている。
例えば、非特許文献２，３では、１６ビットCRCにおいて、各符号長に対して符号の未検出誤り確率が最小となるような生成多項式が提案されている。
また、非特許文献５，８には、符号長ｎを変化させた場合、最小ハミング距離dminが変化する符号長を境に未検出誤り確率Ｐudが極端に変わるという特性があることが示されている。この特性を図６に示す。図６においては、１６ビットCRCにおける最小（限界）の未検出誤り確率が示されている。
図６の横軸は符号長ｎ（ビット）を表し、縦軸は未検出誤り確率Ｐudを表す。図６の点線はCRC-CCITT規格で採用される生成多項式G(x)＝x16＋x12＋x5＋１を各符号長のデータに対して用いた場合の未検出誤り確率を表し、実線は１６ビットCRCにおける理論上の限界の未検出誤り確率を表す。
特許文献１には、CRC生成多項式の選択方法に関する発明が開示されている。この発明においては、生成多項式の次数が与えられたとき、その次数の全ての生成多項式に対して計算したdistance spectrum（距離スペクトル）を元に生成多項式が選択される。distance spectrumはそれぞれのハミング距離における符号語の数を表したテーブルである。これにより、最大・最小ハミング距離を持つ、未検出誤り確率を最小化する生成多項式が選択される。
特許文献２には、与えられた符号長およびCRCパリティ長において、未検出誤り確率ができるだけ低く、最小ハミング距離ができるだけ大きく、かつ、できるだけ広い符号長範囲において使用できる生成多項式の選択方法が開示されている。
J.K.Wolf, R.D.Blakeney,"An exact evaluation of the probability of undetected error for certain shortened binary CRC codes,"Military Communications Conference,1988. MILCOM 88, Conference record. '21st Century Military Communications - What's Possible?'. 1988 IEEE, vol.1, pp.287-292, Oct.1988. T.Baicheva, S.Dodunekov, P.Kazakov,"Undetected error probability performance of cyclic redundancy-check codes of 16-bitredundancy,"IEE Proc.-Commun. ,vol.147, no.5, pp.253-256, Oct.2000. P.Kazakov, "Fast Calculation of the Number of Minimum-Weight Words of CRC Codes,"IEEE Trans.Inform.Theory, vol.47, no.3 ,pp.1190-1195, Mar.2001. P.Koopman,"Cyclic Redundancy Code(CRC) Polynomial Selection For Embedded Networks,"The International Conference on Dependable System and Networks, DSN-2004. G.Castagnoli, J.Ganz, P.Graber,"Optimum Cyclic Redundancy-Check Codes with 16-Bit Redundancy,"IEEE Trans.Commun. , vol.38, no.1, pp.111-114, Jan.1990. G.Funk,"Determination of Best Shortened Codes,"IEEE Trans.Commun. ,vol.44 ,no.1 ,pp.1-6 ,Jan.1996. D.Chun, J.K.Wolf,"Special Hardware for Computing the Probability of Undetected Error for Certain CRC Codes and Test Results,"IEEE Trans.Commun. , vol.42, no.10, pp.2769-2772, Oct.1994. G.Castagnoli, S.Brauer, M.Herrmann,"Optimum of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits,"IEEE Trans.Commun. , vol.41, no.6, pp.883-892, Jun.1993. 米国特許第6,085,349号明細書 特開２００６−１８０１７２号公報
上述したように、CRCの性能（未検出誤り確率、確実に誤り検出が可能なビット数）は生成多項式と符号長によって決まる。全ての符号長において未検出誤り確率や最小ハミング距離が最適となる生成多項式は存在せず、符号長に応じて最適な生成多項式は異なる。つまり、広く用いられているCRC-CCITT規格やANSI規格、および、非特許文献４〜８に示される生成多項式は、未検出誤り確率や最小ハミング距離が最適となる符号長の範囲が限られる。
また、図６に示されるように、CRC-CCITT規格などで採用される生成多項式は、符号長が長く、数千ビット以上のデータを対象とした場合に未検出誤り確率が最小となるように設計されており、符号長が数千ビットにも満たない短いデータを対象とした場合にはさらに良い性能を示す生成多項式が存在する。
さらに、実際のシステムにおいては、様々な符号長やCRCパリティ長が使用されるが、これまで、全ての符号長やCRCパリティ長について最適な生成多項式が明らかになっている訳ではなく、現在知られている生成多項式だけでは実際のシステムにおいて最小の未検出誤り確率を得る上で必ずしも十分ではなかった。
ヘッダデータやサブヘッダデータがユーザデータに付加されることによって構成される情報を単位として行われる一般的な通信システムにおいては、ヘッダデータとサブヘッダデータの両方でCRCを使用したり、ヘッダデータとユーザデータの両方でCRCを使用したりすることは頻繁に行われる。
しかし、そのような場合であっても単一の生成多項式が用いられることが一般的であり、現実に実用化されている通信システムでは、対象とするデータの符号長の変化に対応させて生成多項式を変化させるようなことは行われていない。特許文献２には生成多項式を符号長に応じて選択する方法が開示されているが、そのような、対象とするデータの符号長の変化に対応させて生成多項式を選択するといったことについては必ずしも十分な検討がなされているとはいえない。
符号長が大きく異なる複数のデータを対象として、符号長が長い場合に未検出誤り確率が最小となるように設計されたCRC-CCITT規格などで採用されている生成多項式を単一で用いた場合、当然、短い符号長のデータを対象とした際には、限界値から大きく劣化した未検出誤り確率性能しか得られないことになる。
例えば、IEEE802.15.3c規格で規定されるヘッダデータやサブヘッダデータは数百ビットの符号長のデータであるが、このような数百ビットの符号長のデータに対してCRC-CCITT規格で採用されるものと同じ生成多項式を用いて処理を行うとした場合、その未検出誤り確率は、符号長が数百ビット付近の特性として図６に示されるように理論上の限界値とはかなり離れたものになる。
本発明はこのような状況に鑑みてなされたものであり、特に、対象とするデータの符号長が比較的短い場合においても、限界値に近い未検出誤り確率特性が得られる生成多項式を用いて処理を行うことができるようにするものである。
本発明の一側面の送信装置は、符号長の異なる複数のデータのそれぞれを対象としたCRC符号化処理用の複数の生成多項式を有し、対象とするデータに応じて生成多項式を切り替えてCRC符号化処理を行うCRC符号化処理手段と、前記CRC符号化処理手段によりCRC符号化処理が行われることによって得られたデータを送信する送信手段とを備え、前記CRC符号化処理手段は、第１の符号長の第１のデータ用の第１の生成多項式と、第２の符号長の第２のデータ用の第２の生成多項式とを前記複数の生成多項式として有し、対象とするデータが前記第１のデータであるか前記第２のデータであるかに応じて前記第１と第２の生成多項式を切り替えてCRC符号化処理を行い、前記第１の生成多項式は、前記第１の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式であり、前記第２の生成多項式は、前記第２の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式である。
本発明の一側面の送信方法またはプログラムは、第１の符号長の第１のデータ用の第１の生成多項式と、第２の符号長の第２のデータ用の第２の生成多項式とを前記複数の生成多項式として有し、対象とするデータが前記第１のデータであるか前記第２のデータであるかに応じて前記第１と第２の生成多項式を切り替えるように、対象とするデータに応じて生成多項式を切り替えてCRC符号化処理を行い、CRC符号化処理を行うことによって得られたデータを送信するステップを含む。前記第１の生成多項式は、前記第１の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式であり、前記第２の生成多項式は、前記第２の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式である。
本発明の他の側面の受信装置は、送信装置から送信されてきた信号に基づいてデータを取得する取得手段と、符号長の異なる複数のデータのそれぞれを対象としたCRC処理用の複数の生成多項式を有し、前記取得手段により取得されたデータに応じて生成多項式を切り替えてCRC処理を行うことによってデータの誤りを検出するCRC処理手段とを備え、前記CRC処理手段は、第１の符号長の第１のデータ用の第１の生成多項式と、第２の符号長の第２のデータ用の第２の生成多項式とを前記複数の生成多項式として有し、前記取得手段により取得されたデータが前記第１のデータであるか前記第２のデータであるかに応じて前記第１と第２の生成多項式を切り替えてCRC処理を行い、前記第１の生成多項式は、前記第１の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式であり、前記第２の生成多項式は、前記第２の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式である。
本発明の他の側面の受信方法またはプログラムは、送信装置から送信されてきた信号に基づいてデータを取得し、第１の符号長の第１のデータ用の第１の生成多項式と、第２の符号長の第２のデータ用の第２の生成多項式とを前記複数の生成多項式として有し、取得したデータが前記第１のデータであるか前記第２のデータであるかに応じて前記第１と第２の生成多項式を切り替えるように、取得したデータに応じて生成多項式を切り替えてCRC処理を行うことによってデータの誤りを検出するステップを含む。前記第１の生成多項式は、前記第１の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式であり、前記第２の生成多項式は、前記第２の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式である。
本発明の一側面においては、対象とするデータが第１のデータであるか第２のデータであるかに応じて前記第１と第２の生成多項式を切り替えるように、対象とするデータに応じて生成多項式を切り替えてCRC符号化処理が行われ、CRC符号化処理が行われることによって得られたデータが送信される。
本発明の他の側面においては、送信装置から送信されてきた信号に基づいてデータが取得され、取得されたデータが第１のデータであるか第２のデータであるかに応じて第１と第２の生成多項式を切り替えるように、取得されたデータに応じて生成多項式を切り替えてCRC処理を行うことによってデータの誤りが検出される。
本発明によれば、限界値に近い未検出確率特性が得られる生成多項式を用いて処理を行うことができる。
図７は、本発明の一実施形態に係る送受信システムの構成例を示すブロック図である。
図７の送受信システムは、データの送信側の装置である送信装置１０１と、データの受信側の装置である受信装置１０２から構成される。図７の送受信システムにおいては、例えば、６０GHz帯のミリ波を使った無線通信規格であるIEEE802.15.3c規格に従ってデータの送受信が行われる。
送信装置１０１は、ビデオデータ、オーディオデータなどの送信対象のデータであるユーザデータや、ヘッダデータ、サブヘッダデータに対してCRC符号化処理、誤り訂正符号化処理、伝送路符号化処理を適宜施し、それらの処理を施して得られたデータを送信する。
送信装置１０１には、ヘッダデータを対象としてCRC符号化処理を行うときに用いるヘッダデータ用の生成多項式と、サブヘッダデータを対象としてCRC符号化処理を行うときに用いるサブヘッダデータ用の生成多項式が設定されており、CRC符号化処理の対象とするデータに応じて生成多項式が切り替えられる。
ヘッダデータ用の生成多項式は、ヘッダデータの符号長と同じ例えば１７６ビットのデータに用いたときに未検出誤り確率が低くなる生成多項式であり、サブヘッダデータ用の生成多項式は、サブヘッダデータの符号長と同じ例えば６５６ビットのデータに用いたときに未検出誤り確率が低くなる生成多項式である。それぞれの生成多項式の選択の仕方については後述する。
送信装置１０１から送信されたデータは、空間を伝送路として受信装置１０２により受信される。
受信装置１０２は、受信信号からデータを検出し、検出したデータに対して伝送路復号処理、誤り訂正復号処理を施すことによって受信データを取得する。取得された受信データは、受信装置１０２により、または、受信装置１０２に接続される外部の装置により、その再生や記録などに用いられる。
また、受信装置１０２は、受信データを対象としてCRC処理を行うことによって、データの誤りを検出する。受信装置１０２に対しても、送信装置１０１と同様にヘッダデータ用の生成多項式とサブヘッダデータ用の生成多項式が設定されており、CRC処理に用いる生成多項式が切り替えられるようになされている。
このように、対象とするデータがヘッダデータであるかサブヘッダデータであるかに応じて生成多項式が切り替えられて送信装置１０１においてCRC符号化処理が行われ、受信装置１０２においてCRC処理が行われるようにすることにより、信頼性の高いCRCを実現することが可能になる。
図８は、送信装置１０１の構成例を示すブロック図である。
図８に示されるように、送信装置１０１は、制御器１１１、CRC符号器１１２、誤り訂正符号器１１３、および伝送路符号器１１４から構成される。
制御器１１１は、ユーザにより入力されたユーザデータ、ヘッダデータ、サブヘッダデータを所定の順番でCRC符号器１１２に出力する。
また、制御器１１１は、CRC符号器１１２においてCRC符号化処理の対象になっているデータがヘッダデータである場合、ヘッダデータ用の生成多項式を用いてCRC符号化処理を行うことを指示するセレクト信号を出力し、一方、CRC符号化処理の対象になっているデータがサブヘッダデータである場合、サブヘッダデータ用の生成多項式を用いてCRC符号化処理を行うことを指示するセレクト信号を出力するといったように、CRC符号化処理の対象になっているデータに応じて、CRC符号化処理に用いる生成多項式を指示するセレクト信号をCRC符号器１１２に出力する。
CRC符号器１１２は、制御器１１１から供給されたヘッダデータを対象としてCRC符号化処理を行うことによって得られたCRCパリティをヘッダに付加し、サブヘッダデータを対象としてCRC符号化処理を行うことによって得られたCRCパリティをサブヘッダに付加する。
ヘッダデータを対象として行われるCRC符号化処理と、サブヘッダデータを対象として行われるCRC符号化処理においては、制御器１１１から供給されたセレクト信号に従ってそれぞれ異なる生成多項式が用いられる。CRC符号器１１２は、ヘッダ、サブヘッダが付加された所定のフォーマットのデータを誤り訂正符号器１１３に出力する。なお、ユーザデータに対してもCRC符号化処理を施す必要がある場合、そのCRC符号化処理には予め設定されている所定の生成多項式が用いられる。
誤り訂正符号器１１３は、CRC符号器１１２から供給されたデータに対してReed-Solomon符号化処理などの誤り訂正符号化処理を施し、誤り訂正符号化処理を施すことによって得られたデータを伝送路符号器１１４に出力する。
伝送路符号器１１４は、誤り訂正符号器１１３から供給されたデータに対して、伝送路に応じた符号化処理（変調処理等）を施し、得られたデータを送信する。
図９は、図８のCRC符号器１１２のうちのCRCパリティを生成する部分（図３のCRCパリティ生成器３１に相当する部分）の構成例を示す図である。
図９の回路に対しては、ヘッダデータ、またはサブヘッダデータを構成するシリアルデータ（情報ビット系列）が入力される。
図９は、ヘッダデータ用の生成多項式としてG1(x)＝x16＋x14＋x13＋x12＋x8＋x7＋x6＋x5＋x2＋x＋1を用い、サブヘッダデータ用の生成多項式としてG2(x)＝x16＋x12＋x11＋x9＋x5＋x4＋x3＋x2＋1を用いた場合の例を示している。制御器１１１からのセレクト信号が０の値を表す場合、生成多項式G1(x)＝x16＋x14＋x13＋x12＋x8＋x7＋x6＋x5＋x2＋x＋1を用いて演算が行われ、１の値を表す場合、G2(x)＝x16＋x12＋x11＋x9＋x5＋x4＋x3＋x2＋1を用いて演算が行われる。図９において、シフトレジスタを表すブロック内の「Ｄ」の文字の右側の上付きの数字は直列に接続されているシフトレジスタの数を表す。後述する図１１においても同様である。
EXOR回路１２１においては、制御器１１１から入力されたシリアルデータと、シフトレジスタ１２２において２タイミング分だけ遅延された値に基づいて排他的論理和演算が行われる。EXOR回路１２１の演算結果はシリアルデータとして出力されるとともに、AND回路１４９乃至１５８、EXOR回路１２７，１３９，１４５、およびシフトレジスタ１４８に供給される。
EXOR回路１４７においては、シフトレジスタ１４８において１タイミング分だけ遅延された値と、AND回路１５８から供給された値に基づいて排他的論理和演算が行われる。EXOR回路１４７の演算結果はシフトレジスタ１４６に供給される。
EXOR回路１４５においては、シフトレジスタ１４６において１タイミング分だけ遅延された値と、EXOR回路１２１から供給された値に基づいて排他的論理和演算が行われる。EXOR回路１４５の演算結果はシフトレジスタ１４４に供給される。
EXOR回路１４３においては、シフトレジスタ１４４において１タイミング分だけ遅延された値と、AND回路１５７から供給された値に基づいて排他的論理和演算が行われる。EXOR回路１４３の演算結果はシフトレジスタ１４２に供給される。
EXOR回路１４１においては、シフトレジスタ１４２において１タイミング分だけ遅延された値と、AND回路１５６から供給された値に基づいて排他的論理和演算が行われる。EXOR回路１４１の演算結果はシフトレジスタ１４０に供給される。
EXOR回路１３９においては、シフトレジスタ１４０において１タイミング分だけ遅延された値と、EXOR回路１２１から供給された値に基づいて排他的論理和演算が行われる。EXOR回路１３９の演算結果はシフトレジスタ１３８に供給される。
EXOR回路１３７においては、シフトレジスタ１３８において１タイミング分だけ遅延された値と、AND回路１５５から供給された値に基づいて排他的論理和演算が行われる。EXOR回路１３７の演算結果はシフトレジスタ１３６に供給される。
EXOR回路１３５においては、シフトレジスタ１３６において１タイミング分だけ遅延された値と、AND回路１５４から供給された値に基づいて排他的論理和演算が行われる。EXOR回路１３５の演算結果はシフトレジスタ１３４に供給される。
EXOR回路１３３においては、シフトレジスタ１３４において１タイミング分だけ遅延された値と、AND回路１５３から供給された値に基づいて排他的論理和演算が行われる。EXOR回路１３３の演算結果はシフトレジスタ１３２に供給される。
EXOR回路１３１においては、シフトレジスタ１３２において１タイミング分だけ遅延された値と、AND回路１５２から供給された値に基づいて排他的論理和演算が行われる。EXOR回路１３１の演算結果はシフトレジスタ１３０に供給される。
EXOR回路１２９においては、シフトレジスタ１３０においてさらに２タイミング分だけ遅延された値と、AND回路１５１から供給された値に基づいて排他的論理和演算が行われる。EXOR回路１２９の演算結果はシフトレジスタ１２８に供給される。
EXOR回路１２７においては、シフトレジスタ１２８において１タイミング分だけ遅延された値と、EXOR回路１２１から供給された値に基づいて排他的論理和演算が行われる。EXOR回路１２７の演算結果はシフトレジスタ１２６に供給される。
EXOR回路１２５においては、シフトレジスタ１２６において１タイミング分だけ遅延された値と、AND回路１５０から供給された値に基づいて排他的論理和演算が行われる。EXOR回路１２５の演算結果はシフトレジスタ１２４に供給される。
EXOR回路１２３においては、シフトレジスタ１２４において１タイミング分だけ遅延された値と、AND回路１４９から供給された値に基づいて排他的論理和演算が行われる。EXOR回路１２３の演算結果はシフトレジスタ１２２に供給される。
AND回路１４９，１５０，１５３，１５４，１５５，１５８からは、EXOR回路１２１から出力された値とセレクト信号として制御器１１１から出力され、NOT回路１５９において反転された値がともに１である場合には１の値が出力され、それ以外のときには０の値が出力される。
AND回路１５１，１５２，１５６，１５７からは、EXOR回路１２１から出力された値とセレクト信号として制御器１１１から出力された値がともに１である場合には１の値が出力され、それ以外のときには０の値が出力される。
図１０は、受信装置１０２の構成例を示すブロック図である。
図１０に示されるように、受信装置１０２は、符号検出器２０１、伝送路復号器２０２、誤り訂正復号器２０３、CRC検出器２０４、および制御器２０５から構成される。
符号検出器２０１は、受信された信号に基づいてデータを検出し、検出したデータを伝送路復号器２０２に出力する。
伝送路復号器２０２は、符号検出器２０１から供給されたデータに対して、伝送路に応じた復号処理（復調処理等）を施し、得られたデータを誤り訂正復号器２０３に出力する。
誤り訂正復号器２０３は、伝送路復号器２０２から供給されたデータに対して誤り訂正処理を施し、誤り訂正処理を施すことによって得られたデータを受信データとして出力する。受信データには、ユーザデータ、ヘッダデータ、サブヘッダデータが含まれる。誤り訂正復号器２０３から出力された受信データは、受信データの再生や記録などを行う後段の処理部に供給されるとともに、CRC検出器２０４、制御器２０５に供給される。
CRC検出器２０４は、誤り訂正復号器２０３から供給された受信データに対してCRC処理を施し、データの誤りを検出する。CRC検出器２０４は、ヘッダデータを対象としてCRC処理を行う場合、制御器２０５から供給されたセレクト信号に従って選択した生成多項式を用いてその処理を行い、サブヘッダデータを対象としてCRC処理を行う場合、制御器２０５から供給されたセレクト信号に従って選択した生成多項式を用いてその処理を行う。CRC検出器２０４は、検出結果を表す一致信号を後段の処理部に出力する。一致信号は、データの再送信を送信装置１０１に対して要求するか否かを判断するためなどに用いられる。
制御器２０５は、誤り訂正復号器２０３から供給された受信データに基づいて、CRC検出器２０４においてCRC処理の対象になっているデータを特定する。制御器２０５に対しては、CRC検出器２０４に供給されるものと同じ受信データが誤り訂正復号器２０３から供給されてくる。
制御器２０５は、CRC検出器２０４においてCRC処理の対象になっているデータがヘッダデータである場合、ヘッダデータ用の生成多項式を用いてCRC処理を行うことを指示するセレクト信号を出力し、一方、CRC処理の対象になっているデータがサブヘッダデータである場合、サブヘッダデータ用の生成多項式を用いてCRC処理を行うことを指示するセレクト信号を出力するといったように、CRC処理の対象になっているデータに応じて、CRC処理に用いる生成多項式を指示するセレクト信号をCRC検出器２０４に出力する。
図１１は、図１０のCRC検出器２０４のうちのCRCパリティの検査を行う部分（図５のCRCパリティ検査器４１に相当する部分）の構成例を示す図である。
図１１も、ヘッダデータ用の生成多項式としてG1(x)＝x16＋x14＋x13＋x12＋x8＋x7＋x6＋x5＋x2＋x＋1を用い、サブヘッダデータ用の生成多項式としてG2(x)＝x16＋x12＋x11＋x9＋x5＋x4＋x3＋x2＋1を用いた場合の例を示している。制御器２０５からのセレクト信号が０の値を表す場合、生成多項式G1(x)＝x16＋x14＋x13＋x12＋x8＋x7＋x6＋x5＋x2＋x＋1を用いて演算が行われ、１の値を表す場合、G2(x)＝x16＋x12＋x11＋x9＋x5＋x4＋x3＋x2＋1を用いて演算が行われる。
EXOR回路２１１においては、誤り訂正復号器２０３からシリアルデータとして供給された受信データと、シフトレジスタ２３８において２タイミング分だけ遅延された値に基づいて排他的論理和演算が行われる。EXOR回路２１１の演算結果はシフトレジスタ２１２に供給される。
EXOR回路２１３においては、シフトレジスタ２１２において１タイミング分だけ遅延された値と、AND回路２４８から供給された値に基づいて排他的論理和演算が行われる。EXOR回路２１３の演算結果はシフトレジスタ２１４に供給される。
EXOR回路２１５においては、シフトレジスタ２１４において１タイミング分だけ遅延された値と、シフトレジスタ２３８から供給された値に基づいて排他的論理和演算が行われる。EXOR回路２１５の演算結果はシフトレジスタ２１６に供給される。
EXOR回路２１７においては、シフトレジスタ２１６において１タイミング分だけ遅延された値と、AND回路２４７から供給された値に基づいて排他的論理和演算が行われる。EXOR回路２１７の演算結果はシフトレジスタ２１８に供給される。
EXOR回路２１９においては、シフトレジスタ２１８において１タイミング分だけ遅延された値と、AND回路２４６から供給された値に基づいて排他的論理和演算が行われる。EXOR回路２１９の演算結果はシフトレジスタ２２０に供給される。
EXOR回路２２１においては、シフトレジスタ２２０において１タイミング分だけ遅延された値と、シフトレジスタ２３８から供給された値に基づいて排他的論理和演算が行われる。EXOR回路２２１の演算結果はシフトレジスタ２２２に供給される。
EXOR回路２２３においては、シフトレジスタ２２２において１タイミング分だけ遅延された値と、AND回路２４５から供給された値に基づいて排他的論理和演算が行われる。EXOR回路２２３の演算結果はシフトレジスタ２２４に供給される。
EXOR回路２２５においては、シフトレジスタ２２４において１タイミング分だけ遅延された値と、AND回路２４４から供給された値に基づいて排他的論理和演算が行われる。EXOR回路２２５の演算結果はシフトレジスタ２２６に供給される。
EXOR回路２２７においては、シフトレジスタ２２６において１タイミング分だけ遅延された値と、AND回路２４３から供給された値に基づいて排他的論理和演算が行われる。EXOR回路２２７の演算結果はシフトレジスタ２２８に供給される。
EXOR回路２２９においては、シフトレジスタ２２８において１タイミング分だけ遅延された値と、AND回路２４２から供給された値に基づいて排他的論理和演算が行われる。EXOR回路２２９の演算結果はシフトレジスタ２３０に供給される。
EXOR回路２３１においては、シフトレジスタ２３０において２タイミング分だけ遅延された値と、AND回路２４１から供給された値に基づいて排他的論理和演算が行われる。EXOR回路２３１の演算結果はシフトレジスタ２３２に供給される。
EXOR回路２３３においては、シフトレジスタ２３２において１タイミング分だけ遅延された値と、シフトレジスタ２３８から供給された値に基づいて排他的論理和演算が行われる。EXOR回路２３３の演算結果はシフトレジスタ２３４に供給される。
EXOR回路２３５においては、シフトレジスタ２３４において１タイミング分だけ遅延された値と、AND回路２４０から供給された値に基づいて排他的論理和演算が行われる。EXOR回路２３５の演算結果はシフトレジスタ２３６に供給される。
EXOR回路２３７においては、シフトレジスタ２３６において１タイミング分だけ遅延された値と、AND回路２３９から供給された値に基づいて排他的論理和演算が行われる。EXOR回路２３７の演算結果はシフトレジスタ２３８に供給される。
AND回路２３９，２４０，２４３，２４４，２４５，２４８からは、シフトレジスタ２３８において２タイミング分だけ遅延された値とセレクト信号として制御器２０５から出力され、NOT回路２４９において反転された値がともに１である場合には１の値が出力され、それ以外のときには０の値が出力される。
AND回路２４１，２４２，２４６，２４７からは、シフトレジスタ２３８において２タイミング分だけ遅延された値とセレクト信号として制御器２０５から出力された値がともに１である場合には１の値が出力され、それ以外のときには０の値が出力される。
ここで、以上のような構成を有する送信装置１０１と受信装置１０２の処理について説明する。
はじめに、図１２のフローチャートを参照して、データを送信する送信装置１０１の処理について説明する。この処理は、送信装置１０１のユーザにより、ユーザデータ、ヘッダデータ、サブヘッダデータが入力されたときに開始される。
ステップＳ１において、制御器１１１は、ユーザにより入力されたユーザデータ、ヘッダデータ、サブヘッダデータを所定の順番でCRC符号器１１２に出力する。
ステップＳ２において、制御器１１１は、CRC符号化処理の対象になっているデータに応じて、CRC符号化処理に用いる生成多項式を指示するセレクト信号をCRC符号器１１２に出力する。
ステップＳ３において、CRC符号器１１２は、制御器１１１から供給されたセレクト信号に従って生成多項式を切り替え、ヘッダデータを対象として、またはサブヘッダデータを対象としてCRC符号化処理を行う。ヘッダデータ用の生成多項式を用いて行われたCRC符号化処理によって得られたCRCパリティはヘッダに付加され、サブヘッダデータ用の生成多項式を用いて行われたCRC符号化処理によって得られたCRCパリティはサブヘッダに付加される。
ステップＳ４において、誤り訂正符号器１１３は、CRC符号器１１２から供給されたデータに対して誤り訂正符号化処理を施し、誤り訂正符号化処理を施すことによって得られたデータを伝送路符号器１１４に出力する。
ステップＳ５において、伝送路符号器１１４は、誤り訂正符号器１１３から供給されたデータに対して、伝送路に応じた符号化処理を施す。
ステップＳ６において、伝送路符号器１１４は、符号化処理を施すことによって得られたデータを受信装置１０２に送信し、処理を終了させる。
次に、図１３のフローチャートを参照して、データを受信する受信装置１０２の処理について説明する。
ステップＳ１１において、符号検出器２０１は、受信された信号に基づいてデータを検出し、検出したデータを伝送路復号器２０２に出力する。
ステップＳ１２において、伝送路復号器２０２は、符号検出器２０１から供給されたデータに対して、伝送路に応じた復号処理を施し、得られたデータを誤り訂正復号器２０３に出力する。
ステップＳ１３において、誤り訂正復号器２０３は、伝送路復号器２０２から供給されたデータに対して誤り訂正処理を施し、誤り訂正処理を施すことによって得られたデータを受信データとして出力する。
ステップＳ１４において、制御器２０５は、誤り訂正復号器２０３から供給された受信データに基づいて、CRC検出器２０４においてCRC処理の対象になっているデータを特定する。
ステップＳ１５において、制御器２０５は、CRC処理の対象になっているデータに応じて、CRC処理に用いる生成多項式を指示するセレクト信号をCRC検出器２０４に出力する。
ステップＳ１６において、CRC検出器２０４は、制御器２０５から供給されたセレクト信号に従って生成多項式を切り替え、誤り訂正復号器２０３から供給された受信データに対してCRC処理を施す。ヘッダデータを対象としてCRC処理を行う場合、ヘッダデータ用の生成多項式が用いられ、サブヘッダデータを対象としてCRC処理を行う場合、サブヘッダデータ用の生成多項式が用いられる。CRC検出器２０４は、CRC処理の結果を表す一致信号を出力し、処理を終了させる。
以上の処理により、信頼性の高いCRCを実現することが可能になる。
ここで、送信装置１０１のCRC符号器１１２と受信装置１０２のCRC検出器２０４に設定される生成多項式について説明する。
以下、説明の便宜上、生成多項式G(x)の表現の仕方として、係数の並びを１６進数で表したものを採用する。例えば、１６進数の１２Ｄは、それを２進数で表すと１００１０１１０１であるので生成多項式G(x)＝x8＋x5＋x3＋x2＋1を表すことになる。また、生成多項式G(x)の項数をｗとする。相反多項式（reciprocal polynomial：高次の係数と低次の係数を逆転した多項式）は互いに同じ特性を示す。
図１４は、符号長が３６ビットから１４９ビットのデータを対象とした処理において用いられる生成多項式の候補を示す図である。
３６ビットから１４９ビットまでの範囲の所定の符号長のデータを対象として送信装置１０１のCRC符号器１１２においてCRC符号化処理が行われ、受信装置１０２のCRC検出器２０４においてCRC処理が行われる場合、図１４に示される候補の中から選択された生成多項式がCRC符号器１１２とCRC検出器２０４に設定される。
図１４の左から１列目と４列目はインデックスＡ１乃至Ａ３４を表し、２列目と５列目は係数の並びを１６進数で表した生成多項式を表す。３列目と６列目はそれぞれの生成多項式の項数ｗを表す。
例えば、インデックスＡ１の生成多項式G(x)は項数ｗが８である１３６１３（G(x)＝x16＋x13＋x12＋x10＋x9＋x4＋x＋1）であり、インデックスＡ２の生成多項式G(x)は項数ｗが１０である１３Ｄ６５（G(x)＝x16＋x13＋x12＋x11＋x10＋x8＋x6＋x5＋x2＋1）である。
図１５は、図１４の生成多項式を、３６ビットから１４９ビットまでの範囲のそれぞれの符号長のデータを対象とした処理において用いられる生成多項式毎に分けて示す図である。図１５の左側の列は符号長ｎを表し、右側の列は生成多項式G(x)のインデックスを表す。
例えば、３６ビットのデータを対象として送信装置１０１のCRC符号器１１２においてCRC符号化処理が行われ、受信装置１０２のCRC検出器２０４においてCRC処理が行われる場合、図１５の上から２行目に示されるように、インデックスＡ６，Ａ２５−Ａ２９，Ａ３１−Ａ３４の候補の中から選択された生成多項式がCRC符号器１１２とCRC検出器２０４に設定される。同様に、３７ビットのデータを対象としてCRC符号化処理、CRC処理が行われる場合、図１５の上から３行目に示されるように、インデックスＡ６，Ａ１１，Ａ２２，Ａ２５−Ａ３４の候補の中から選択された生成多項式がCRC符号器１１２とCRC検出器２０４に設定される。
図１６は、符号長が１５２ビットから２５５ビットのデータを対象とした処理において用いられる生成多項式の候補を示す図である。
図１６の左から１列目と４列目はインデックスＢ１乃至Ｂ１５を表し、２列目と５列目は係数の並びを１６進数で表した生成多項式を表す。３列目と６列目はそれぞれの生成多項式の項数ｗを表す。
例えば、インデックスＢ１の生成多項式G(x)は項数ｗが１１である１５６Ｆ３（G(x)＝x16＋x14＋x12＋x10＋x9＋x7＋x6＋x5＋x4＋x＋1）であり、インデックスＢ２の生成多項式G(x)は項数ｗが５である１２１０９（G(x)＝x16＋x13＋x8＋x3＋1）である。
図１７は、図１６の生成多項式を、１５２ビットから２５５ビットまでの範囲のそれぞれの符号長のデータを対象とした処理において用いられる生成多項式毎に分けて示す図である。図１７の左側の列は符号長ｎを表し、右側の列は生成多項式G(x)のインデックスを表す。
例えば、１５２ビットから１７０ビットまでの所定の符号長のデータを対象として送信装置１０１のCRC符号器１１２においてCRC符号化処理が行われ、受信装置１０２のCRC検出器２０４においてCRC処理が行われる場合、図１７の上から２行目に示されるように、インデックスＢ１−Ｂ１５の候補の中から選択された生成多項式がCRC符号器１１２とCRC検出器２０４に設定される。同様に、１７１ビットから２５５ビットまでの所定の符号長のデータを対象としてCRC符号化処理、CRC処理が行われる場合、図１７の上から３行目に示されるように、インデックスＢ１−Ｂ１０，Ｂ１４，Ｂ１５の候補の中から選択された生成多項式がCRC符号器１１２とCRC検出器２０４に設定される。
図１８は、符号長が２５８ビットから８００１ビットのデータを対象とした処理において用いられる生成多項式の候補を示す図である。
図１８の左から１列目と４列目はインデックスＣ１乃至Ｃ３６を表し、２列目と５列目は係数の並びを１６進数で表した生成多項式を表す。３列目と６列目はそれぞれの生成多項式の項数ｗを表す。
例えば、インデックスＣ１の生成多項式G(x)は項数ｗが９である１９４１Ｆ（G(x)＝x16＋x15＋x12＋x10＋x4＋x3＋x2＋x＋1）であり、インデックスＣ２の生成多項式G(x)は項数ｗが７である１６０８７（G(x)＝x16＋x14＋x13＋x7＋x2＋x＋1）である。
図１９は、図１８の生成多項式を、２５８ビットから８００１ビットまでの範囲のそれぞれの符号長のデータを対象とした処理において用いられる生成多項式毎に分けて示す図である。図１９の左側の列は符号長ｎを表し、右側の列は生成多項式G(x)のインデックスを表す。
例えば、２５８ビットから５９５ビットまでの所定の符号長のデータを対象として送信装置１０１のCRC符号器１１２においてCRC符号化処理が行われ、受信装置１０２のCRC検出器２０４においてCRC処理が行われる場合、図１９の上から２行目に示されるように、インデックスＣ１−Ｃ３５の候補の中から選択された生成多項式がCRC符号器１１２とCRC検出器２０４に設定される。同様に、５９６ビットから６００ビットまでの所定の符号長のデータを対象としてCRC符号化処理、CRC処理が行われる場合、図１９の上から３行目に示されるように、インデックスＣ１−Ｃ７，Ｃ９−Ｃ３５の候補の中から選択された生成多項式がCRC符号器１１２とCRC検出器２０４に設定される。
図２０は、以上のような候補の中から選択した生成多項式を用いた場合の未検出誤り確率の計算結果を示す図である。
図２０の未検出誤り確率の計算結果は、符号長が１７６ビットのヘッダデータ用の生成多項式として、図１７の上から３行目に示されるインデックスＢ１−Ｂ１０，Ｂ１４，Ｂ１５の候補の中からインデックスＢ４の１７１Ｅ７（G1(x)＝x16＋x14＋x13＋x12＋x8＋x7＋x6＋x5＋x2＋x＋1）を選択し、符号長が６５６ビットのサブヘッダデータ用の生成多項式として、図１９の上から９行目に示されるインデックスＣ１−Ｃ４，Ｃ７，Ｃ１０，Ｃ１３，Ｃ１５−Ｃ３５の候補の中からインデックスＣ３の１１Ａ３Ｄ（G2(x)＝x16＋x12＋x11＋x9＋x5＋x4＋x3＋x2＋1）を選択して１６ビットCRC（１６ビットのCRCパリティ）の生成、または検査を行った場合の結果を示している。すなわち、図２０は、図９、図１１の回路によって生成多項式G1(x)とG2(x)を切り替えて用いた場合の結果を示す。比較のため、CRC-CCITT（G(x)＝x16＋x12＋x5＋１）を用いた場合の未検出誤り確率も示している。
図２０に示されるように、符号長が１７６ビットのヘッダデータに対してCRC符号化処理、CRC処理を施すために用いる生成多項式としてCRC-CCITT（G(x)＝x16＋x12＋x5＋１）を用いた場合、その未検出誤り確率は１．５６×１０-13となるのに対して、１７１Ｅ７（G1(x)＝x16＋x14＋x13＋x12＋x8＋x7＋x6＋x5＋x2＋x＋1）を用いた場合、その未検出誤り確率は１．９９×１０-16となる。
また、符号長が６５６ビットのサブヘッダデータに対してCRC符号化処理、CRC処理を施すために用いる生成多項式としてCRC-CCITT（G(x)＝x16＋x12＋x5＋１）を用いた場合、その未検出誤り確率は２．１７×１０-11となるのに対して、１１Ａ３Ｄ（G2(x)＝x16＋x12＋x11＋x9＋x5＋x4＋x3＋x2＋1）を用いた場合、その未検出誤り確率は１．０５×１０-11となる。
ヘッダデータとサブヘッダデータのいずれを対象とした場合にも、上述した候補の中から選択した生成多項式の未検出誤り確率の方が低く、その確率は図６に示した理論上の限界値に近いものになる。
このように、符号長が１７６ビットのヘッダデータに対してCRC符号化処理、CRC処理を施すために用いる生成多項式として図１６の候補の中から選択したものと、符号長が６５６ビットのサブヘッダデータに対してCRC符号化処理、CRC処理を施すために用いる生成多項式として図１８の候補の中から選択したものを設定し、対象のデータに応じて切り替えて用いるようにすることにより、理論上の限界値付近までCRCの精度を向上させることができる。
なお、ここでは、ヘッダデータ用の生成多項式として図１６の候補の中からインデックスＢ４の１７１Ｅ７を選択し、サブヘッダデータ用の生成多項式として図１８の候補の中からインデックスＣ３の１１Ａ３Ｄを選択するものとしたが、生成多項式の組み合わせは任意である。
また、以上においては、ヘッダデータを対象とするときとサブヘッダデータを対象とするときとで２つの生成多項式を切り替えるものとしたが、CRC符号化処理またはCRC処理の対象とするそれぞれ符号長の異なるデータがさらにある場合、それぞれのデータ用の生成多項式を送信装置１０１と受信装置１０２に予め設定しておき、それらの生成多項式を切り替えるようにしてもよい。
図２１は、以上のような生成多項式を選択する情報処理装置３０１の構成例を示すブロック図である。
情報処理装置３０１は例えばパーソナルコンピュータである。CPU(Central Processing Unit)３１１、ROM(Read Only Memory)３１２、RAM(Random Access Memory)３１３は、バス３１４により相互に接続されている。
バス３１４には、さらに、入出力インタフェース３１５が接続されている。入出力インタフェース３１５には、キーボード、マウスなどよりなる入力部３１６、ディスプレイなどよりなる出力部３１７、ハードディスクや不揮発性のメモリよりなる記憶部３１８、ネットワークインタフェースなどよりなる通信部３１９、光ディスクや半導体メモリなどのリムーバブルメディア３２１を駆動するドライブ３２０が接続されている。
以上のように構成される情報処理装置３０１では、CPU３１１が、例えば記憶部３１８に記憶されているプログラムを入出力インタフェース３１５及びバス３１４を介してRAM３１３にロードして実行することにより、生成多項式を選択する処理が行われる。
次に、図２２のフローチャートを参照して、生成多項式を選択する情報処理装置３０１の処理について説明する。この処理は、基本的には、本出願人による特願２００４−３７０７９６号（特開２００６−１８０１７２号公報（特許文献２））に記載されている生成多項式の選択処理と同様の処理である。
すなわち、ステップＳ５１において、情報処理装置３０１のCPU３１１は、符号長ｎにおいて最小ハミング距離dmin＝最小ハミング距離の最大値Max.dminの条件を満たす生成多項式を全検索によって抽出する。最小ハミング距離dminは生成多項式によって異なり、その値が大きいほど、ランダム誤り検出能力が高く、未検出誤り確率が低い。最小ハミング距離の最大値Max.dminは、特許文献２にも記載されているように符号長ｎによって変わる値である。ステップＳ５１において行われる抽出処理の詳細については図２３のフローチャートを参照して後述する。
ステップＳ５２において、CPU３１１は、ステップＳ５１で抽出した生成多項式の中から、未検出誤り確率Ｐudが小さい順に例えば１０個の生成多項式を選択し、処理を終了させる。ステップＳ５２において選択された生成多項式が、図１４、図１６、図１８に示されるような生成多項式の候補となる。
次に、図２３のフローチャートを参照して、図２２のステップＳ５１において行われる抽出処理について説明する。
ステップＳ６１において、CPU３１１は、符号長ｎにおける生成多項式の候補G'(x)を生成する。
ステップＳ６２において、CPU３１１は、生成多項式の候補G'(x)が、既に検索済み、すなわち、ステップＳ６３以降の処理の対象として用いた生成多項式の相反多項式であるか否かを判定する。
CPU３１１は、生成多項式の候補G'(x)が、既に検索済みの生成多項式の相反多項式であるとステップＳ６２において判定した場合、ステップＳ６１に戻り、異なる生成多項式の候補G'(x)を生成して同様の処理を繰り返す。ある生成多項式と、その相反多項式は未検出誤り確率などの点で同じ性能を有することから、既に検索済みの生成多項式と同じ性能を有する生成多項式の候補G'(x)を対象としては以降の処理は行われないことになる。
一方、生成多項式の候補G'(x)が、既に検索済みの生成多項式の相反多項式ではないとステップＳ６２において判定した場合、ステップＳ６３において、CPU３１１は、生成多項式の候補G'(x)の項数ｗが、最小ハミング距離の最大値Max.dmin未満であるか否かを判定する。
CPU３１１は、生成多項式の候補G'(x)の項数ｗが、最小ハミング距離の最大値Max.dmin未満であるとステップＳ６３において判定した場合、ステップＳ６１に戻り、異なる生成多項式の候補G'(x)を生成して同様の処理を繰り返す。上述したように最小ハミング距離の最大値Max.dminは符号長ｎによって変わる値であり、この値より項数ｗが小さいということは、いま注目している生成多項式の候補G'(x)の最小ハミング距離dminは最小ハミング距離の最大値Max.dminより小さく、生成多項式の候補G'(x)が、ここで検索の対象としている最小ハミング距離dmin＝最小ハミング距離の最大値Max.dminの条件を満たす生成多項式ではないことになる。最小ハミング距離dmin＝ｍを実現するには、項数ｗとしてｍ以上の値が必要になる。
一方、生成多項式の候補G'(x)の項数ｗが、最小ハミング距離の最大値Max.dmin未満ではないとステップＳ６３において判定した場合、ステップＳ６４において、CPU３１１は、生成多項式の候補G'(x)の双対符号の、上式（５）で用いる重み分布Ｂを求める。重み分布Ｂについては上述したように非特許文献１に開示されている。
ステップＳ６５において、CPU３１１は、生成多項式の候補G'(x)の最小ハミング距離dminを求める。
ステップＳ６６において、CPU３１１は、求めた最小ハミング距離dminが、最小ハミング距離の最大値Max.dmin未満であるか否かを判定する。
CPU３１１は、最小ハミング距離dminが、最小ハミング距離の最大値Max.dmin未満であるとステップＳ６６において判定した場合、ステップＳ６１に戻り、異なる生成多項式の候補G'(x)を生成して同様の処理を繰り返す。
一方、ステップＳ６６において、最小ハミング距離dminが、最小ハミング距離の最大値Max.dmin未満ではない、すなわち、いま注目している生成多項式の候補G'(x)が、最小ハミング距離dmin＝最小ハミング距離の最大値Max.dminの条件を満たす生成多項式であると判定した場合、ステップＳ６７において、CPU３１１は、未検出誤り確率Ｐudを上式（５）に従って求める。上式（４）に従って未検出誤り確率Ｐudが求められるようにしてもよい。
ステップＳ６８において、CPU３１１は、検索の対象としていない生成多項式の候補G'(x)がまだ存在するか否かを判定する。
CPU３１１は、以上のような検索の対象としていない生成多項式の候補G'(x)がまだ存在するとステップＳ６８において判定した場合、ステップＳ６１に戻り、異なる生成多項式の候補G'(x)を生成して同様の処理を繰り返す。
一方、全ての生成多項式の候補G'(x)を対象として以上のような検索を行ったことから、ステップＳ６８において、生成多項式の候補G'(x)が存在しないと判定した場合、CPU３１１は、図２２のステップＳ５１に戻り、それ以降の処理を行う。
上述した一連の処理は、ハードウエアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、専用のハードウエアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な汎用のパーソナルコンピュータなどに、プログラム記録媒体からインストールされる。
CPU３１１が実行するプログラムは、例えばリムーバブルメディア３２１に記録して、あるいは、ローカルエリアネットワーク、インターネット、デジタル放送といった、有線または無線の伝送媒体を介して提供され、記憶部３１８にインストールされる。
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
送受信システムの構成例を示すブロック図である。 図１のCRC符号器の構成例を示す図である。 図２のCRCパリティ生成器の構成例を示す回路図である。 図１のCRC検出器の構成例を示す図である。 図４のCRCパリティ検査器の構成例を示す回路図である。 未検出誤り確率の計算結果の例を示す図である。 本発明の一実施形態に係る送受信システムの構成例を示すブロック図である。 図７の送信装置の構成例を示すブロック図である。 図８のCRC符号器のうちのCRCパリティを生成する部分の構成例を示す回路図である。 図７の受信装置の構成例を示すブロック図である。 図１０のCRC検出器のうちのCRCパリティの検査を行う部分の構成例を示す回路図である。 送信装置の処理について説明するフローチャートである。 受信装置の処理について説明するフローチャートである。 生成多項式の候補を示す図である。 図１４の生成多項式の候補を符号長毎に分けて示す図である。 生成多項式の候補を示す他の図である。 図１６の生成多項式の候補を符号長毎に分けて示す図である。 生成多項式の候補を示すさらに他の図である。 図１８の生成多項式の候補を符号長毎に分けて示す図である。 未検出誤り確率の計算結果を示す図である。 情報処理装置の構成例を示すブロック図である。 情報処理装置の生成多項式の選択処理について説明するフローチャートである。 図２２のステップＳ５１において行われる抽出処理について説明するフローチャートである。
符号の説明
１０１ 送信装置， １０２ 受信装置， １１１ 制御器， １１２ CRC符号器， １１３ 誤り訂正符号器， １１４ 伝送路符号器， ２０１ 符号検出器， ２０２ 伝送路復号器， ２０３ 誤り訂正復号器， ２０４ CRC検出器， ２０５ 制御器

Claims (6)

  1. 符号長の異なる複数のデータのそれぞれを対象としたCRC符号化処理用の複数の生成多項式を有し、対象とするデータに応じて生成多項式を切り替えてCRC符号化処理を行うCRC符号化処理手段と、
    前記CRC符号化処理手段によりCRC符号化処理が行われることによって得られたデータを送信する送信手段と
    を備え、
    前記CRC符号化処理手段は、第１の符号長の第１のデータ用の第１の生成多項式と、第２の符号長の第２のデータ用の第２の生成多項式とを前記複数の生成多項式として有し、対象とするデータが前記第１のデータであるか前記第２のデータであるかに応じて前記第１と第２の生成多項式を切り替えてCRC符号化処理を行い、
    前記第１の生成多項式は、前記第１の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式であり、
    前記第２の生成多項式は、前記第２の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式である
    送信装置。
  2. 符号長の異なる複数のデータのそれぞれを対象としたCRC符号化処理用の複数の生成多項式を有する送信装置の送信方法において、
    第１の符号長の第１のデータ用の第１の生成多項式と、第２の符号長の第２のデータ用の第２の生成多項式とを前記複数の生成多項式として有し、対象とするデータが前記第１のデータであるか前記第２のデータであるかに応じて前記第１と第２の生成多項式を切り替えるように、対象とするデータに応じて生成多項式を切り替えてCRC符号化処理を行い、
    CRC符号化処理を行うことによって得られたデータを送信する
    ステップを含み、
    前記第１の生成多項式は、前記第１の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式であり、
    前記第２の生成多項式は、前記第２の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式である
    送信方法。
  3. 符号長の異なる複数のデータのそれぞれを対象としたCRC符号化処理用の複数の生成多項式を有する送信装置の処理をコンピュータに実行させるプログラムにおいて、
    第１の符号長の第１のデータ用の第１の生成多項式と、第２の符号長の第２のデータ用の第２の生成多項式とを前記複数の生成多項式として有し、対象とするデータが前記第１のデータであるか前記第２のデータであるかに応じて前記第１と第２の生成多項式を切り替えるように、対象とするデータに応じて生成多項式を切り替えてCRC符号化処理を行い、
    CRC符号化処理を行うことによって得られたデータを送信する
    ステップを含み、
    前記第１の生成多項式は、前記第１の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式であり、
    前記第２の生成多項式は、前記第２の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式である
    処理をコンピュータに実行させるプログラム。
  4. 送信装置から送信されてきた信号に基づいてデータを取得する取得手段と、
    符号長の異なる複数のデータのそれぞれを対象としたCRC処理用の複数の生成多項式を有し、前記取得手段により取得されたデータに応じて生成多項式を切り替えてCRC処理を行うことによってデータの誤りを検出するCRC処理手段と
    を備え、
    前記CRC処理手段は、第１の符号長の第１のデータ用の第１の生成多項式と、第２の符号長の第２のデータ用の第２の生成多項式とを前記複数の生成多項式として有し、前記取得手段により取得されたデータが前記第１のデータであるか前記第２のデータであるかに応じて前記第１と第２の生成多項式を切り替えてCRC処理を行い、
    前記第１の生成多項式は、前記第１の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式であり、
    前記第２の生成多項式は、前記第２の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式である
    受信装置。
  5. 符号長の異なる複数のデータのそれぞれを対象としたCRC処理用の複数の生成多項式を有する受信装置の受信方法において、
    送信装置から送信されてきた信号に基づいてデータを取得し、
    第１の符号長の第１のデータ用の第１の生成多項式と、第２の符号長の第２のデータ用の第２の生成多項式とを前記複数の生成多項式として有し、取得したデータが前記第１のデータであるか前記第２のデータであるかに応じて前記第１と第２の生成多項式を切り替えるように、取得したデータに応じて生成多項式を切り替えてCRC処理を行うことによってデータの誤りを検出する
    ステップを含み、
    前記第１の生成多項式は、前記第１の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式であり、
    前記第２の生成多項式は、前記第２の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式である
    受信方法。
  6. 符号長の異なる複数のデータのそれぞれを対象としたCRC処理用の複数の生成多項式を有する受信装置の処理をコンピュータに実行させるプログラムにおいて、
    送信装置から送信されてきた信号に基づいてデータを取得し、
    第１の符号長の第１のデータ用の第１の生成多項式と、第２の符号長の第２のデータ用の第２の生成多項式とを前記複数の生成多項式として有し、取得したデータが前記第１のデータであるか前記第２のデータであるかに応じて前記第１と第２の生成多項式を切り替えるように、取得したデータに応じて生成多項式を切り替えてCRC処理を行うことによってデータの誤りを検出する
    ステップを含み、
    前記第１の生成多項式は、前記第１の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式であり、
    前記第２の生成多項式は、前記第２の符号長における最小ハミング距離の最大値とその最小ハミング距離が等しい生成多項式であって、未検出誤り確率が低い順に所定の数だけ選択された生成多項式の中から選択された生成多項式である
    処理をコンピュータに実行させるプログラム。
JP2008096273A 2008-04-02 2008-04-02 送信装置および方法、受信装置および方法、並びにプログラム Expired - Fee Related JP4798164B2 (ja)

Priority Applications (5)

Application Number Priority Date Filing Date Title
JP2008096273A JP4798164B2 (ja) 2008-04-02 2008-04-02 送信装置および方法、受信装置および方法、並びにプログラム
EP09727863.4A EP2264905A4 (en) 2008-04-02 2009-04-02 TRANSMISSION DEVICE AND METHOD, RECEIVING DEVICE AND METHOD AND PROGRAM THEREFOR
PCT/JP2009/056881 WO2009123280A1 (ja) 2008-04-02 2009-04-02 送信装置および方法、受信装置および方法、並びにプログラム
US12/934,159 US9209931B2 (en) 2008-04-02 2009-04-02 Device and method for transmission, device and method for reception, and program
CN2009801121320A CN101983481B (zh) 2008-04-02 2009-04-02 用于发送的设备和方法、用于接收的设备和方法以及程序

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2008096273A JP4798164B2 (ja) 2008-04-02 2008-04-02 送信装置および方法、受信装置および方法、並びにプログラム

Publications (2)

Publication Number Publication Date
JP2009253440A JP2009253440A (ja) 2009-10-29
JP4798164B2 true JP4798164B2 (ja) 2011-10-19

Family

ID=41135647

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2008096273A Expired - Fee Related JP4798164B2 (ja) 2008-04-02 2008-04-02 送信装置および方法、受信装置および方法、並びにプログラム

Country Status (5)

Country Link
US (1) US9209931B2 (ja)
EP (1) EP2264905A4 (ja)
JP (1) JP4798164B2 (ja)
CN (1) CN101983481B (ja)
WO (1) WO2009123280A1 (ja)

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2571172A4 (en) 2010-05-11 2013-10-16 Asip Solutions Inc METHOD AND DEVICE FOR PROCESSING ERROR CORRECTION CODES
EP2963829B1 (en) * 2013-05-07 2018-07-11 Huawei Technologies Co., Ltd. Coding and decoding method, device and system
EP3622645B1 (en) * 2017-05-12 2021-11-03 Telefonaktiebolaget LM Ericsson (publ) Adaptive crc length for beam sweeping
US10530396B2 (en) 2017-11-20 2020-01-07 International Business Machines Corporation Dynamically adjustable cyclic redundancy code types
US10530523B2 (en) 2017-11-20 2020-01-07 International Business Machines Corporation Dynamically adjustable cyclic redundancy code rates
US10541782B2 (en) 2017-11-20 2020-01-21 International Business Machines Corporation Use of a cyclic redundancy code multiple-input shift register to provide early warning and fail detection
US10419035B2 (en) 2017-11-20 2019-09-17 International Business Machines Corporation Use of multiple cyclic redundancy codes for optimized fail isolation

Family Cites Families (46)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4763332A (en) * 1987-03-02 1988-08-09 Data Systems Technology Corp. Shared circuitry for the encoding and syndrome generation functions of a Reed-Solomon code
JP2816223B2 (ja) * 1990-03-02 1998-10-27 株式会社日立製作所 セル同期回路
JPH04211547A (ja) * 1990-03-20 1992-08-03 Fujitsu Ltd 同期回路
JP2998366B2 (ja) * 1991-12-03 2000-01-11 富士通株式会社 Ｃｒｃチェック方法
JPH10117147A (ja) * 1996-10-09 1998-05-06 Nec Corp エラーチェック用データ発生回路
JPH10233700A (ja) * 1997-02-20 1998-09-02 Oki Electric Ind Co Ltd Ｃｒｃ誤り検出方法、ｃｒｃ誤り検出システム、監視制御方法及び監視制御システム
DE19736434C3 (de) * 1997-08-21 2002-08-22 Nokia Mobile Phones Ltd Verfahren und Vorrichtungen zur Erkennung der Position von in einem seriellen Datenempfangsstrom liegenden Datenpaketen
US6085349A (en) 1997-08-27 2000-07-04 Qualcomm Incorporated Method for selecting cyclic redundancy check polynomials for linear coded systems
US6192498B1 (en) * 1997-10-01 2001-02-20 Globepan, Inc. System and method for generating error checking data in a communications system
WO2000044105A1 (en) * 1999-01-21 2000-07-27 Samsung Electronics Co., Ltd. A communication apparatus and method for a cdma communication system
US6530057B1 (en) * 1999-05-27 2003-03-04 3Com Corporation High speed generation and checking of cyclic redundancy check values
US6681364B1 (en) * 1999-09-24 2004-01-20 International Business Machines Corporation Cyclic redundancy check for partitioned frames
TW498312B (en) * 1999-09-29 2002-08-11 Sony Corp Disc-shaped recording medium, data recording device and method thereof, and data recovery device
US6456875B1 (en) * 1999-10-12 2002-09-24 Medtronic, Inc. Cyclic redundancy calculation circuitry for use in medical devices and methods regarding same
JP2001285076A (ja) * 2000-03-31 2001-10-12 Ando Electric Co Ltd Ｃｒｃ符号演算回路、及びｃｒｃ符号演算方法
GB2372337B (en) * 2000-08-18 2004-10-20 Sgs Thomson Microelectronics Error checking
US6848072B1 (en) * 2000-09-19 2005-01-25 Bbn Solutions Llc Network processor having cyclic redundancy check implemented in hardware
US6732317B1 (en) * 2000-10-23 2004-05-04 Sun Microsystems, Inc. Apparatus and method for applying multiple CRC generators to CRC calculation
US6931581B1 (en) * 2000-10-25 2005-08-16 Sun Microsystems, Inc. Method for superimposing a sequence number in an error detection code in a data network
US6684363B1 (en) * 2000-10-25 2004-01-27 Sun Microsystems, Inc. Method for detecting errors on parallel links
JP2002141809A (ja) * 2000-10-31 2002-05-17 Ando Electric Co Ltd Ｃｒｃ符号演算回路、及びｃｒｃ符号演算方法
JP2002164791A (ja) * 2000-11-27 2002-06-07 Ando Electric Co Ltd Ｃｒｃ符号演算回路、及びｃｒｃ符号演算方法
US6701478B1 (en) * 2000-12-22 2004-03-02 Nortel Networks Limited System and method to generate a CRC (cyclic redundancy check) value using a plurality of CRC generators operating in parallel
US6810501B1 (en) * 2001-01-03 2004-10-26 Juniper Networks, Inc. Single cycle cyclic redundancy checker/generator
US6732318B2 (en) * 2001-04-03 2004-05-04 Sun Microsystems, Inc. Variable width parallel cyclical redundancy check
US6820228B1 (en) * 2001-06-18 2004-11-16 Network Elements, Inc. Fast cyclic redundancy check (CRC) generation
US6988161B2 (en) * 2001-12-20 2006-01-17 Intel Corporation Multiple port allocation and configurations for different port operation modes on a host
US7246303B2 (en) * 2002-03-25 2007-07-17 Intel Corporation Error detection and recovery of data in striped channels
US6961893B1 (en) * 2002-03-28 2005-11-01 Adaptec, Inc. Separable cyclic redundancy check
US7162675B2 (en) * 2002-04-05 2007-01-09 Lucent Technologies Inc. Error detection methods in wireless communication systems
EP2175559A1 (en) * 2002-04-22 2010-04-14 Fujitsu Limited Error-detecting decoder with re-calculation of a remainder upon partial re-transmission of a data string.
US6938197B2 (en) * 2002-08-01 2005-08-30 Lattice Semiconductor Corporation CRC calculation system and method for a packet arriving on an n-byte wide bus
US7290196B1 (en) * 2003-03-21 2007-10-30 Cypress Semiconductor Corporation Cyclical redundancy check using nullifiers
US7191383B2 (en) * 2003-03-28 2007-03-13 International Business Machines Corporation System and method for optimizing iterative circuit for cyclic redundancy check (CRC) calculation
US7571370B2 (en) * 2003-06-19 2009-08-04 Lsi Logic Corporation Configurable, fast, 32-bit CRC generator for 1-byte to 16-bytes variable width input data
US7523305B2 (en) * 2003-12-17 2009-04-21 International Business Machines Corporation Employing cyclic redundancy checks to provide data security
US7249306B2 (en) * 2004-02-20 2007-07-24 Nvidia Corporation System and method for generating 128-bit cyclic redundancy check values with 32-bit granularity
US7546512B2 (en) * 2004-09-23 2009-06-09 Intel Corporation Techniques to perform error detection
JP4379329B2 (ja) * 2004-12-22 2009-12-09 ソニー株式会社 Ｃｒｃ生成多項式の選択方法、ｃｒｃ符号化方法およびｃｒｃ符号化回路
US7583664B2 (en) * 2004-12-28 2009-09-01 Michael Ho Techniques for transmitting and receiving traffic over advanced switching compatible switch fabrics
US7363573B1 (en) * 2005-01-10 2008-04-22 Xilinx, Inc. Method and apparatus for a dedicated cyclic redundancy check block within a device
US7761776B1 (en) * 2005-11-03 2010-07-20 Xilinx, Inc. Method and apparatus for a modular, programmable cyclic redundancy check design
JP4764973B2 (ja) * 2005-12-09 2011-09-07 独立行政法人産業技術総合研究所 Ｃｒｃ値の算出装置
US7916641B2 (en) * 2006-06-29 2011-03-29 Wi-Lan, Inc. System and process for packet delineation
US8341510B2 (en) * 2007-06-22 2012-12-25 Sony Corporation CRC generator polynomial select method, CRC coding method and CRC coding circuit
JP5298621B2 (ja) * 2007-12-21 2013-09-25 ソニー株式会社 送信装置および方法、受信装置および方法

Also Published As

Publication number Publication date
WO2009123280A1 (ja) 2009-10-08
CN101983481B (zh) 2013-11-20
US20110029838A1 (en) 2011-02-03
JP2009253440A (ja) 2009-10-29
US9209931B2 (en) 2015-12-08
EP2264905A1 (en) 2010-12-22
CN101983481A (zh) 2011-03-02
EP2264905A4 (en) 2016-01-20

Similar Documents

Publication Publication Date Title
US8327251B2 (en) Transmission apparatus and method, reception apparatus and method, and program
JP4798164B2 (ja) 送信装置および方法、受信装置および方法、並びにプログラム
US8341510B2 (en) CRC generator polynomial select method, CRC coding method and CRC coding circuit
US11025278B2 (en) Polar coding encoding/decoding method and apparatus
US20190260507A1 (en) Error detection in wireless communications using sectional redundancy check information
JP4701343B2 (ja) トレリスに基づく受信器
US20200028524A1 (en) Polar code encoding/decoding method and encoding/decoding apparatus
KR102662470B1 (ko) 조기 종료를 위해 극성 코드에서 분산 crc를 인터리빙하는 시스템 및 방법
KR20080043679A (ko) 에러 정정 방법 및 이에 적합한 장치
JP2022022398A (ja) セクション式冗長検査を有する制御シグナリングの符号化および復号
JP4379329B2 (ja) Ｃｒｃ生成多項式の選択方法、ｃｒｃ符号化方法およびｃｒｃ符号化回路
JPWO2013027483A1 (ja) 誤り訂正復号装置
CN114978198B (zh) 基于外码辅助的级联随机接入译码方法及相关设备
JP2007129679A (ja) Ｑｃ符号の符号化方法
JP3734486B2 (ja) 誤り訂正装置および誤り訂正方法
Baicheva Determination of the best CRC codes with up to 10-bit redundancy
CN111865492B (zh) 中继系统中的信息传输方法、装置、设备及存储介质
EP2075918A2 (en) Transmission apparatus and method, reception apparatus and method, and program
JP4286274B2 (ja) 誤り訂正装置
KR102214397B1 (ko) 순회 부호의 블라인드 판별 방법 및 그 장치
JP6552776B1 (ja) 誤り訂正復号装置および誤り訂正復号方法
JPH11298335A (ja) 誤り訂正回路
US8503585B2 (en) Decoding method and associated apparatus
Baicheva et al. CRC codes for error control
JP2007215153A (ja) 通信システム

Legal Events

Date Code Title Description
A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20110426

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20110614

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20110705

A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20110718

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20140812

Year of fee payment: 3

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20140812

Year of fee payment: 3

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

LAPS Cancellation because of no payment of annual fees