(57)【要約】  【課題】  ＣＲＣ符号化回路に適した生成多項式Ｇ（ｘ）を選択する。  【解決手段】  ＣＲＣ生成多項式の選択方法は、ｋビットの情報語を持ち、該情報語についてｒビットのパリティが付加された符号長（ｎ）の符号の各符号長（ｎ）における最小ハミング距離（d min ）の最大値である最大・最小ハミング距離（Ｍａｘ．d min ）を求め、Ｍａｘ．d min の変化する符号長ｎを求め、そのｎの範囲（ｎmin ≦ｎ≦ｎmax ）を求める。ｎの範囲において、常に、d min＝Ｍａｘ．d min を満たす生成多項式（Ｇ（ｘ））を全検索によって見いだし、全検索によって見いだしたＧ（ｘ）の中から、項数（ｗ）、符号の未検出誤り確率（Ｐud）も最小のものを選び出す。【選択図】  図８
2006180172.tif 000002
【特許請求の範囲】
【請求項１】
ＣＲＣ符号および／またはＣＲＣ符号結果をＣＲＣ検査するために用いる生成多項式を選択する方法であって、
ｋビットの情報語を持ち、該情報語についてｒビットのパリティが付加された符号長（ｎ）の符号の各符号長（ｎ）における最小ハミング距離（d min ）の最大値である最大・最小ハミング距離（Ｍａｘ．d min ）を求める第１工程と、
符号の最大・最小ハミング距離（Ｍａｘ．d min ）の変化する符号長（ｎ）を求め、その符号長ｎの範囲（ｎmin （ｒ，Ｍａｘ．d min ）≦ｎ≦ｎmax （ｒ，Ｍａｘ．d min ））を求める第２工程と、
前記符号長（ｎ）の範囲（ｎmin （ｒ，Ｍａｘ．d min ）≦ｎ≦ｎmax （ｒ，Ｍａｘ．d min ））において、常に、符号の最小ハミング距離（d min ）が最大・最小ハミング距離（Ｍａｘ．d min ）と等しい条件（d min ＝Ｍａｘ．d min ）を満たす生成多項式（Ｇ（ｘ））を全検索によって見いだす第３工程と、
前記全検索によって見いだした生成多項式（Ｇ（ｘ））の中から、項数（ｗ）、符号の未検出誤り確率（Ｐud）も最小のものを選び出す第４工程と
を備えたＣＲＣ生成多項式の選択方法。
【請求項２】
前記第３および第４工程は、
周期（ｐ）が最大符号長（ｎmax （ｒ，Ｍａｘ．d min ））以上であり（ｐ≧ｎmax （ｒ，Ｍａｘ．d min ））、かつ、（ｎmax ，ｎmax −ｒ）の符号について最小ハミング距離（d min ）が最大・最小ハミング距離（Ｍａｘ．d min ）と等しい条件（d min ＝Ｍａｘ．d min ）を満たす生成多項式Ｇ（ｘ）を全検索により見付ける工程と、
前記全検索により見いだした生成多項式（Ｇ（ｘ））の中から、項数（ｗ）が最小の生成多項式（Ｇ（ｘ））を選ぶ工程と、
前記選択した生成多項式（Ｇ（ｘ））について、符号の未検出誤り確率（Ｐud）が最小になる生成多項式（Ｇ（ｘ））を見いだす工程と、
を有する、
請求項１に記載のＣＲＣ生成多項式の選択方法。
【請求項３】
前記生成多項式Ｇ（ｘ）を検索および選択する工程において、最大・最小ハミング距離（Ｍａｘ．d min ）がＭａｘ．d min ＝２については、周期（ｐ）が最大周期２r −１をもつ（原始多項式である）生成多項式Ｇ（ｘ）の中で、生成多項式の項数ｗ、および、符号の未検出誤り確率Ｐudが最小である生成多項式Ｇ（ｘ）を選択する
請求項２に記載のＣＲＣ生成多項式の選択方法。
【請求項４】
請求項１〜３いずれかにおいて、ｎmin ≠ｎmax である、
ＣＲＣ生成多項式の選択方法。
【請求項５】
請求項１〜３いずれかに記載のＣＲＣ生成多項式の選択方法により、下記のいずれかの生成多項式Ｇ（ｘ）が選択された、ＣＲＣ生成多項式の選択方法。
１．ｒ＝３、ｎ＝４のとき、生成多項式Ｇ（ｘ）＝ｘ3＋ｘ2＋ｘ＋１である、
２．ｒ＝６、ｎ＝７のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である、
３．ｒ＝６、ｎ＝８のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ4＋ｘ2＋ｘ＋１（相反多項式：ｘ6＋ｘ5＋ｘ4＋ｘ2＋１）である、
４．ｒ＝６、ｎ＝８のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ4＋ｘ3＋ｘ＋１（相反多項式：ｘ6＋ｘ5＋ｘ3＋ｘ2＋１）である、
５．ｒ＝６、ｎ＝８のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ5＋ｘ3＋ｘ＋１である、
６．ｒ＝８、ｎ＝９のとき、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である、
７．ｒ＝１０、ｎ＝１１のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である、
８．ｒ＝１０、ｎ＝１２のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ8＋ｘ6＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ4＋ｘ2＋１）である、
９．ｒ＝１２、ｎ＝１３のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である、
１０．ｒ＝１２、ｎ＝１４のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ10＋ｘ8＋ｘ6＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ8＋ｘ6＋ｘ4＋ｘ2＋１）である、
１１．ｒ＝１４、ｎ＝１５のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である、
１２．ｒ＝１４、ｎ＝１６のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ12＋ｘ10＋ｘ9＋ｘ7＋ｘ5＋ｘ4＋ｘ3＋ｘ＋１（相反多項式：ｘ14＋ｘ13＋ｘ11＋ｘ10＋ｘ9＋ｘ7＋ｘ5＋ｘ4＋ｘ2＋１）である、
１３．ｒ＝１４、ｎ＝１７のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ11＋ｘ8＋ｘ6＋ｘ5＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ9＋ｘ8＋ｘ6＋ｘ3＋１）である、
１４．ｒ＝１６、ｎ＝１７のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ15＋ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である、
１５．ｒ＝１６、ｎ＝１８のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ14＋ｘ12＋ｘ10＋ｘ8＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ16＋ｘ15＋ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ10＋ｘ8＋ｘ6＋ｘ4＋ｘ2＋１）である、
１６．ｒ＝１６、ｎ＝２２のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ8＋ｘ7＋ｘ6＋ｘ4＋ｘ2＋ｘ＋１（相反多項式：ｘ16＋ｘ15＋ｘ14＋ｘ12＋ｘ10＋ｘ9＋ｘ8＋ｘ3＋１）である。
【請求項６】
請求項４において、下記のいずれかの生成多項式Ｇ（ｘ）が選択された、ＣＲＣ生成多項式の選択方法。
１．ｒ＝４、６≦ｎ≦７のとき、生成多項式Ｇ（ｘ）＝ｘ4＋ｘ2＋ｘ＋１（相反多項式：ｘ4＋ｘ3＋ｘ2＋１）である、
２．ｒ＝６、９≦ｎ≦３１のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ2＋ｘ＋１（相反多項式：ｘ6＋ｘ5＋ｘ4＋１）である、
３．ｒ＝８、１０≦ｎ≦１２のとき、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ5＋ｘ4＋ｘ3＋ｘ＋１（相反多項式：ｘ8＋ｘ7＋ｘ5＋ｘ4＋ｘ3＋１）である、
４．ｒ＝８、１０≦ｎ≦１２のとき、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ6＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ2＋１）である、
５．ｒ＝８、１８≦ｎ≦１２７のとき、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ4＋ｘ＋１（相反多項式：ｘ8＋ｘ7＋ｘ4＋１）である、
６．ｒ＝８、ｎ≧１２８のとき、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ5＋ｘ3＋ｘ2＋１（相反多項式：ｘ8＋ｘ6＋ｘ5＋ｘ3＋１）である、
７．ｒ＝１０、２３≦ｎ≦３１のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ9＋ｘ3＋ｘ＋１（相反多項式：ｘ10＋ｘ9＋ｘ7＋ｘ＋１）である、
８．ｒ＝１０、３２≦ｎ≦５１１のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ5＋ｘ2＋１（相反多項式：ｘ10＋ｘ8＋ｘ5＋１）である、
９．ｒ＝１０、ｎ≧５１２のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ3＋１（相反多項式：ｘ10＋ｘ7＋１）である、
１０．ｒ＝１２、２４≦ｎ≦３９のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ11＋ｘ7＋ｘ3＋ｘ＋１（相反多項式：ｘ12＋ｘ11＋ｘ9＋ｘ5＋ｘ＋１）である、
１１．ｒ＝１２、４０≦ｎ≦６５のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ10＋ｘ7＋ｘ6＋ｘ5＋ｘ2＋１である、
１２．ｒ＝１２、６６≦ｎ≦２０４７のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ7＋ｘ2＋１（相反多項式：ｘ12＋ｘ10＋ｘ5＋１）である、
１３．ｒ＝１２、ｎ≧２０４８のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ7＋ｘ6＋ｘ4＋１（相反多項式：ｘ12＋ｘ8＋ｘ6＋ｘ5＋１）である、
１４．ｒ＝１４、２８≦ｎ≦７１のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ10＋ｘ9＋ｘ6＋ｘ2＋１（相反多項式：ｘ14＋ｘ12＋ｘ8＋ｘ5＋ｘ4＋１）である、
１５．ｒ＝１４、７２≦ｎ≦１２７のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ11＋ｘ5＋ｘ3＋１（相反多項式：ｘ14＋ｘ11＋ｘ9＋ｘ3＋１）である、
１６．ｒ＝１４、１２８≦ｎ≦８１９１のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ5＋ｘ2＋１（相反多項式：ｘ14＋ｘ12＋ｘ9＋１）である、
１７．ｒ＝１４、ｎ≧８１９２のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ6＋ｘ4＋ｘ＋１（相反多項式：ｘ14＋ｘ13＋ｘ10＋ｘ8＋１）である、
１８．ｒ＝１６、１９≦ｎ≦２１のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ12＋ｘ9＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ2＋１（相反多項式：ｘ16＋ｘ14＋ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ7＋ｘ4＋ｘ3＋１）である、
１９．ｒ＝１６、１９≦ｎ≦２１のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ12＋ｘ9＋ｘ7＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋１（相反多項式：ｘ16＋ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ9＋ｘ7＋ｘ4＋ｘ3＋１）である、
２０．ｒ＝１６、２３≦ｎ≦３１のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ11＋ｘ5＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ16＋ｘ15＋ｘ14＋ｘ13＋ｘ11＋ｘ5＋ｘ3＋１）である、
２１．ｒ＝１６、３６≦ｎ≦１５１のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ15＋ｘ13＋ｘ8＋ｘ5＋ｘ3＋ｘ＋１（相反多項式：ｘ16＋ｘ15＋ｘ13＋ｘ11＋ｘ8＋ｘ3＋ｘ＋１）である、
２２．ｒ＝１６、１５２≦ｎ≦２５７のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ15＋ｘ8＋ｘ＋１である、
２３．ｒ＝１６、２５８≦ｎ≦３２７６７のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ2＋１（相反多項式：ｘ16＋ｘ14＋ｘ3＋１）である、
２４．ｒ＝１６、ｎ≧３２７６８のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ9＋ｘ7＋ｘ4＋１（相反多項式：ｘ16＋ｘ12＋ｘ9＋ｘ7＋１）である。
【請求項７】
請求項１〜６いずれかにより選択された生成多項式Ｇ（ｘ）を用いたＣＲＣ符号化を行う、ＣＲＣ符号化方法。
【請求項８】
請求項１〜６いずれかにより選択された生成多項式Ｇ（ｘ）を、シフトレジスタと前記生成多項式Ｇ（ｘ）の係数に応じて設けられた排他的論理和回路と巡回的に接続し、かつ、前記生成多項式Ｇ（ｘ）の係数に応じて設けられた排他的論理和回路に、最終段の排他的論理和回路の出力を入力する回路構成を持つ、
ＣＲＣ符号化回路。
【請求項９】
次数（パリティ数）ｒ、周期ｐの生成多項式Ｇ（ｘ）を用いて符号長ｎのＣＲＣ符号の符号化を行うＣＲＣ符号化方法であって、
符号長ｎおよび次数ｒによって規定されるＣＲＣ符号の最小ハミング距離最大値Ｍａｘ．d min 、次数ｒのもとで符号の最小ハミング距離最大値Ｍａｘ．d min が一定となる符号長ｎの範囲をｎmin ≦ｎ≦ｎmax としたとき（ただし、ｎmin は最小符号長であり、ｎmax は最大符号長である）、周期ｐ≧最大符号長ｎmax 、もしくは、周期ｐ＝２r −１、かつ、ｎmin ≦ｎ≦ｎmax の条件下において、
符号の最小ハミング距離d min がd min ＝Ｍａｘ．d min を満たす生成多項式Ｇ（ｘ）のなかで、生成多項式Ｇ（ｘ）の項数が最小となり、かつ、２次元対称通信路における符号の未検出誤り確率が最小となる生成多項式Ｇ（ｘ）を用いる、
ＣＲＣ符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを符号処理する符号化方法とその装置に関する。
特に、本発明は、ディジタルデータを、磁気テープ記録装置や光ディスク装置等に記録再生するとき、または、無線伝送システム等によって伝送する際に、符号化を行うことによって、伝送路において生じた誤りを検出するＣＲＣ符号の発生に用いる生成多項式を選択する方法と、選択した生成多項式を用いてＣＲＣ符号化するＣＲＣ符号およびＣＲＣ符号化回路に関する。
【背景技術】
【０００２】
情報記録装置や通信装置などで情報（データ）を伝送路を経由して伝送するとき、伝送された情報に誤りが生じることがある。
情報に誤りが起こったかどうかを検出する方法として広く用いられている技術として、ＣＲＣ（Cyclic Redundancy Check：巡回冗長検査）がある。
【０００３】
ＣＲＣを行うためには、伝送すべき情報を予めＣＲＣ符号化しておく必要がある。
図１を参照してＣＲＣ符号化について述べる。
図１において、送信装置１と受信装置３とが伝送路２を介して接続されている。
ＣＲＣは、送信装置１において、情報語（データ）にＣＲＣパリティを付加したＣＲＣ符号に対して、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号などの誤り訂正符号化を施すことで、誤り訂正復号による誤訂正の検出に用いられる。
送信装置１において、伝送すべきＣＲＣ符号化の対象となる、複数の情報語（データ）が連続する、入力情報系列がＣＲＣ符号器１１に入力され、ＣＲＣ符号化される。ＣＲＣ符号器１１の詳細は図２を参照して後述する。ＣＲＣ符号化された情報は次に誤り訂正符号器１２に入力され、たとえば、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号などの誤り訂正符号化される。誤り訂正符号化された情報は次に伝送路符号器１３に入力され、伝送路２に応じた伝送路符号化処理がなされ、伝送路２へと送られる。
伝送路２を経由した信号は、受信装置３の符号検出器３１によって検出され、検出された情報が伝送路復号器３２に入力される。伝送路復号器３２によって伝送路復号された検出情報系列は誤り訂正復号器３３によって、誤り訂正符号器１２の処理に対応して、たとえば、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号などの誤り訂正が行われる。誤り訂正された情報は次にＣＲＣ検出器３４に入力される。ＣＲＣ検出器３４は、誤り訂正された検出系列に対してＣＲＣ処理を行い、誤り訂正が正しく行われたかどうか（検出系列に誤りがあるかどうか）を判定し、その結果を一致信号として出力する。
ＣＲＣ検出器３４の詳細は図５を参照して後述する。
【０００４】
ＣＲＣ検出器３４から出力された一致信号は、たとえば、情報記録装置のドライブのコントローラにおいて再送信要求を行うなどによる信頼性向上に用いられる。
ＣＲＣ符号のその他の用途として、たとえば、符号検出器におけるポストプロセッサの一部として用いられたり、ヘッダ情報や、パケット通信における送信パケットに対しても用いられる。また、誤り訂正用の消失フラグとしても用いられる。
【０００５】
ＣＲＣ符号による誤り検出原理
ＣＲＣ符号による誤り検出原理を説明する。
ｋビットからなる情報語（ディジタルデータ）にｒビットのパリティを付加して符号長ｎ（ｎ＝ｋ＋ｒ）ビットの符号語とするとき、情報語を多項式で表現した（ｋ−１）次（order)の情報多項式Ｍ（ｘ）にｘrを乗じる。たとえば、情報語が２進数で「１０１０１０１」の場合、情報多項式Ｍ（ｘ）は、ｘ6＋ｘ4＋ｘ2＋１と表記される。
情報多項式Ｍ（ｘ）にｘrを乗じた結果Ｍ（ｘ）・ｘrを、ｒ次の生成多項式（generator polynomial）Ｇ（ｘ）で割った際の剰余多項式Ｒ（ｘ）（次数は（ｒ−１）次）と、商多項式Ｑ（ｘ）を用いて下記式１に従って求めることにより、（ｎ−１）次の符号多項式Ｗ（ｘ）を下記式２のように構成する。
【０００６】
［数１］
Ｍ（ｘ）・ｘr ＝Ｑ（ｘ）・Ｇ（ｘ）＋Ｒ（ｘ）
・・・（１）
【０００７】
［数２］
Ｗ（ｘ）＝Ｍ（ｘ）・ｘr −Ｒ（ｘ）
・・・（２）
【０００８】
式１、２の関係から、符号多項式はＷ（ｘ）＝Ｑ（ｘ）Ｇ（ｘ）となる。よって、符号多項式Ｗ（ｘ）は生成多項式Ｇ（ｘ）で割り切れる。
【０００９】
以上の観点の下、たとえば、図１の送信装置１が伝送路２を介して受信装置３に符号多項式Ｗ（ｘ）を送信したものを受信装置３が受信した際に、受信装置３のＣＲＣ検出器３４において、受信多項式Ｙ（ｘ）が生成多項式Ｇ（ｘ）で割り切れるかどうかを調べる。
受信多項式Ｙ（ｘ）が生成多項式Ｇ（ｘ）で割り切れれば、受信多項式Ｙ（ｘ）は符号多項式Ｗ（ｘ）に一致しており、伝送路２において情報語に誤りが発生しなかったと推定できるが、受信多項式Ｙ（ｘ）が生成多項式Ｇ（ｘ）で割り切れなければ、受信多項式Ｙ（ｘ）は符号多項式Ｗ（ｘ）ではないので、伝送路２において情報語に誤りが生じたと判定できる（推定できる）。
【００１０】
ＣＲＣ符号は、巡回符号であるため、生成多項式Ｇ（ｘ）が定まれば、その回路構成は、たとえば、図１における送信装置１のＣＲＣ符号器１１の回路構成は、シフトレジスタと排他的論理和を用いて比較的容易に装置化することが可能である。
【００１１】
ＣＲＣ符号器の例
ＣＲＣにおいて広く用いられている生成多項式Ｇ（ｘ）としては、１６ビットＣＲＣであるＣＲＣ−ＣＣＩＴＴ規格に基づく、Ｇ（ｘ）＝ｘ16＋ｘ12＋ｘ5＋１、または、ＣＲＣ−ＡＮＳＩ規格に基づく、Ｇ（ｘ）＝ｘ16＋ｘ15＋ｘ2＋１などである。
【００１２】
以下、例示として、パリティビット数（次数）ｒ＝３とした場合の生成多項式Ｇ（ｘ）＝ｘ3＋ｘ＋１とした場合の、たとえば、図１における送信装置１におけるＣＲＣ符号器（ＣＲＣ符号化回路）１１の構成例を図２を参照して述べる。
図２は情報多項式Ｍ（ｘ）から符号多項式Ｗ（ｘ）を生成するＣＲＣ符号器１１の構成例を示す図である。
ＣＲＣ符号器１１は、ＣＲＣパリティ生成器１１０、第１セレクタ１１１、第２セレクタ１１２、および、ビット数カウンタ１１３を有する。
ＣＲＣパリティ生成器１１０は、ｋビットの情報ビット系列についてｒビットのＣＲＣパリティを発生して第１セレクタ１１１に出力する。ＣＲＣパリティ生成器１１０におけるパリティの発生方法については図３および図４を参照して述べる。
第２セレクタ１１２は、「０」入力端子にｋビットの情報ビット系列が入力されている期間は、ビット数カウンタ１１３からの状態制御信号Ｓ１に基づいて、入力された情報ビット系列を出力する。また、第２セレクタ１１２は、「０」入力端子への情報ビット系列の入力が終了したとき、「１」入力端子に、第１セレクタ１１１を経由して入力されるＣＲＣパリティ生成器１１０で生成したｒビットのパリティを出力する。このように、ＣＲＣ符号器１１の第２セレクタ１１２からは、「ｋビットの情報ビット系列」と、それに続く、「情報ビット系列に基づいてＣＲＣパリティ生成器１１０で生成されたｒビットのパリティビット」とが出力される。このように、第２セレクタ１１２から出力される符号ビット系列は、「ｋビットの情報ビット系列」と、「ｒビットのパリティビット」とからなる、符号長ｎ＝ｋ＋ｒの符号ビット系列となる。
【００１３】
ＣＲＣパリティ生成器１１０および第１セレクタ１１１について述べる。
図３は、生成多項式Ｇ（ｘ）をＧ（ｘ）＝ｘ3＋ｘ＋１とした場合のＣＲＣパリティ生成器１１０の回路例を示す。
図３のＣＲＣパリティ生成器１１０は、第１シフトレジスタＲ００、第１排他的論理和（ＥＸＯＲ）回路ＥＸＯＲ１、第２シフトレジスタＲ０１、第３シフトレジスタＲ０２、および、第２排他的論理和回路ＥＸＯＲ２が巡回状に接続されており、第２排他的論理和回路ＥＸＯＲ２の出力が第１排他的論理和回路ＥＸＯＲ１に入力されている。
【００１４】
なお、生成多項式Ｇ（ｘ）＝ｘ4＋ｘ3＋ｘ2＋ｘ＋１とした場合のＣＲＣパリティ生成器１１０の回路図の例を図４に示す。
図４のＣＲＣパリティ生成器１１０は、第１シフトレジスタＲ００、第１排他的論理和（ＥＸＯＲ）回路ＥＸＯＲ１、第２シフトレジスタＲ０１、第２排他的論理和回路ＥＸＯＲ２、第３シフトレジスタＲ０２、第３排他的論理和回路ＥＸＯＲ３、第４シフトレジスタＲ０３、第４排他的論理和回路ＥＸＯＲ４が巡回状に接続されており、第４排他的論理和回路ＥＸＯＲ４の出力が第１、２、３排他的論理和回路ＥＸＯＲ１、ＥＸＯＲ２、ＥＸＯＲ３に入力されている。
【００１５】
図３および図４に図解したように、ＣＲＣパリティ生成器１１０は生成多項式Ｇ（ｘ）に基づいて構成される。換言すれば、図３および図４の図解から理解できるように、生成多項式Ｇ（ｘ）が定まれば、ＣＲＣパリティ生成器１１０は、シフトレジスタと排他的論理和回路を巡回的かつ最終段の排他的論理和回路、たとえば、図３の第２排他的論理和回路ＥＸＯＲ２または図４の第４排他的論理和回路ＥＸＯＲ４の出力をその前段の排他的論理和回路に印加する回路として構成できる。
以下、図３に図解したＣＲＣパリティ生成器１１０の動作について述べる。図４に図解したＣＲＣパリティ生成器１１０の動作も図３に図解したＣＲＣパリティ生成器１１０の動作と基本的には同様である。
【００１６】
図３において、情報多項式Ｍ（ｘ）によって表される情報ビット系列を、第３シフトレジスタＲ０２の上位の第２排他的論理和回路ＥＸＯＲ２に、毎時刻、たとえば、シフトレジスタを動作させる毎クロック毎に、１ビットずつ情報ビット系列の高次の項から順に入力することで、情報多項式Ｍ（ｘ）に予めｘrが乗じられた形のビット系列Ｍ（ｘ）・ｘrが、ＣＲＣパリティ生成器１１０に入力されることになる。
ここで、第１〜第３シフトレジスタＲ００，Ｒ０１，Ｒ０２の初期値はゼロである。
情報ビット系列の零次の項をＣＲＣパリティ生成器１１０に入力し終えた時点での第１〜第３シフトレジスタＲ００，Ｒ０１，Ｒ０２に保持されている値が剰余多項式Ｒ（ｘ）の各次数の係数を与える。すなわち、剰余多項式Ｒ（ｘ）は、Ｒ（ｘ）＝（Ｒ０２の保持内容）×ｘ2＋（Ｒ０１の保持内容）×ｘ＋（Ｒ００の保持内容）となる。
そのため、この情報ビット系列の零次の項をＣＲＣパリティ生成器１１０に入力し終えた時点で、図２に図示しない制御回路から出力されるイネーブル信号Ｅ０がディセーブル（不活性状態）となり、ＣＲＣパリティ生成器１１０の第１〜第３シフトレジスタＲ００，Ｒ０１，Ｒ０２に保持されている値は保持されて、第１セレクタ１１１に出力される。
【００１７】
図２において、たとえば、図３に回路構成を例示したＣＲＣパリティ生成器１１０から第１セレクタ１１１の３個入力端子００、０１、１０への出力は、ＣＲＣパリティ生成器１１０の各シフトレジスタＲ００，Ｒ０１，Ｒ０２の出力Ｒ００out，Ｒ０１out，Ｒ０２outであり、第１セレクタ１１１は、図２に図示しない制御回路から出力される第１セレクト信号Ｓ０に従って、３個の入力端子００、０１、１０に入力されたＣＲＣパリティ生成器１１０からの出力Ｒ００out，Ｒ０１out，Ｒ０２outの１つを順に選択して第２セレクタ１１２の「１」入力端子に出力する。
第２セレクタ１１２は、図２に図示しない制御回路から制御されるビット数カウンタ１１３から出力される第２セレクト信号Ｓ１に従って、換言すれば、ビット数カウンタ１１３のビット計数値に応じて、第２セレクタ１１２の「０」入力端子にｋビットの情報ビット系列を入力する期間は「０」入力端子に入力される情報ビット系列を選択して情報ビット系列をそのまま出力する。他方、情報ビット系列をＣＲＣパリティ生成器１１０に入力し終わり、全てのパリティが生成されたタイミングには、第２セレクタ１１２の「１」入力端子に入力された第１セレクタ１１１の出力、すなわち、ＣＲＣパリティ生成器１１０で生成したパリティを選択して、出力する。
【００１８】
このようにして、たとえば、図２のＣＲＣ符号器１１における第２セレクタ１１２から出力される符号ビット系列は、上述したように、「ｋビットの情報ビット系列」と、「ｒビットのパリティビット」とからなる、符号長ｎ＝ｋ＋ｒの符号ビット系列となる。
たとえば、図１の送信装置１において、上述したように、ＣＲＣ符号器１１においてＣＲＣ符号化された符号ビット系列は、誤り訂正符号器１２に入力され、たとえば、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号などの誤り訂正符号化され、誤り訂正符号化された情報が伝送路符号器１３に入力されて伝送路２に応じた伝送路符号化処理がなされ、伝送路２へと送られる。
伝送路２を経由した信号は、受信装置３の符号検出器３１によって検出され、検出された情報が伝送路復号器３２に入力される。伝送路復号器３２によって伝送路復号された検出情報系列は誤り訂正復号器３３によって誤り訂正が行われる。誤り訂正された情報はＣＲＣ検出器３４において検出系列に誤りがあるかどうか）を判定される。
【００１９】
図５は、受信多項式Ｙ（ｘ）に誤りがないかどうかを検査するＣＲＣ検出器３４の構成例を示す図である。
ＣＲＣ検出器３４は、ＣＲＣパリティ検査器３４１と、比較器３４２とを有する。
ＣＲＣパリティ検査器３４１は、上述したように、受信多項式Ｙ（ｘ）が生成多項式Ｇ（ｘ）で割り切れるかどうかを調べ、受信多項式Ｙ（ｘ）が生成多項式Ｇ（ｘ）で割り切れれば、受信多項式Ｙ（ｘ）は符号多項式Ｗ（ｘ）に一致しており、伝送路２において情報語に誤りが発生しなかったと判定し、受信多項式Ｙ（ｘ）が生成多項式Ｇ（ｘ）で割り切れなければ、受信多項式Ｙ（ｘ）は符号多項式Ｗ（ｘ）ではないので、伝送路２において情報語に誤りが生じたと判定する。
ＣＲＣパリティ検査器３４１は、受信多項式Ｙ（ｘ）を生成多項式Ｇ（ｘ）で割る回路であり、比較器３４２はＣＲＣパリティ検査器３４１で割った結果に剰余があるか否かをチェックする回路である。
【００２０】
ＣＲＣパリティ検査器３４１の構成例を図６に示す。
ＣＲＣ検出器３４は図１のＣＲＣ検出器３４に対応しており、図６に図解したＣＲＣパリティ検査器３４１の構成は、図３に図解したＣＲＣパリティ生成器１１０に対応している。ＣＲＣパリティ生成器１１０が図４の回路構成の場合は、ＣＲＣパリティ検査器３４１もそれに則した回路構成となる。以下、図３に図解したＣＲＣパリティ生成器１１０に対応したＣＲＣパリティ検査器３４１について述べる。
図６に図解したＣＲＣパリティ検査器３４１は、第１の排他的論理和回路ＥＸＯＲ１１、第１シフトレジスタＲ１０、第２の排他的論理和回路ＥＸＯＲ１２、第２シフトレジスタＲ１１、第３シフトレジスタＲ１２が巡回状に接続されており、かつ、第３シフトレジスタＲ１２の出力が第２の排他的論理和回路ＥＸＯＲ１２に入力される回路構成をしている。
図６のＣＲＣパリティ検査器３４１において、受信多項式Ｙ（ｘ）によって表される受信ビット系列を、第１シフトレジスタＲ１０の右端の第１の排他的論理和回路ＥＸＯＲ１１に毎時刻ごと１ビットずつ高次の項から順に入力する。受信ビット系列の零次の項をＣＲＣパリティ検査器３４１に入力し終えた時点での第１〜第３シフトレジスタＲ１０，Ｒ１１，Ｒ１２の値が剰余多項式Ｒ（ｘ）の係数を与える。すなわち、Ｒ（Ｘ）＝（Ｒ１２の値）×ｘ2＋（Ｒ１１の値）×ｘ＋（Ｒ１０の値）。
ここで、第１〜第３シフトレジスタＲ１０，Ｒ１１，Ｒ１２の初期値はゼロである。
【００２１】
図５において、ＣＲＣパリティ検査器３４１から比較器３４２への出力、Ｒ１０out，Ｒ１１out，Ｒ１２outは、図６のＣＲＣパリティ検査器３４１の各レジスタＲ１０，Ｒ１１，Ｒ１２の出力である。
比較器３４２は、Ｒ１０out，Ｒ１１out，Ｒ１２outの全値がゼロ、つまり剰余がゼロかどうかを比較し（チェックし）、Ｒ１０out，Ｒ１１out，Ｒ１２outの値全てがゼロであったかどうかを表す１ビットの一致信号を出力する。すなわち、Ｒ１０out，Ｒ１１out，Ｒ１２outの値全てがゼロであった場合は、受信多項式Ｙ（ｘ）は符号多項式Ｗ（ｘ）に一致しており、伝送路２において情報語に誤りが発生しなかったと判定した、比較器３４２から、たとえば、論理「１」の一致信号が出力され、そうでなかったときは、たとえば、論理「０」の一致信号が出力される。
【００２２】
ＣＲＣの誤り検出能力は、一般的に、ランダム誤り検出能力とバースト誤り検出能力および符号の未検出誤り確率Ｐudで評価され、これらは生成多項式Ｇ（ｘ）と符号長ｎによって決まる。
【００２３】
ここで、符号の未検出誤り確率Ｐudとは、伝送路上で生じた誤りによって、受信語が、送信した符号語とは別の符号語（与えられた情報ビットとは別の情報ビットに対してＣＲＣパリティを計算して付加した符号語）に変化してしまう確率のことを言う。別の符号語に変化してしまうことにより、ＣＲＣを行っても剰余がゼロとなってしまう。つまり、受信語に誤りがあるのに誤りなしと判定してしまうということが起こる。
たとえば、非特許文献１に開示されているように、符号の未検出誤り確率Ｐudは、次数（パリティ数）ｒ、符号長ｎ、生成多項式Ｇ（ｘ）と符号長ｎが決まると求まる重み分布Ａ、もしくは双対符号（dual code）の重み分布Ｂ、２元対称通信路（Binary Symmetric Channel）におけるチャネルビット誤り確率（遷移確率）εによって以下のように表される。
【００２４】
【数３】
2006180172.tif 000003
【００２５】
【数４】
2006180172.tif 000004
【００２６】
ランダム誤り検出能力については、（d min−１）個以下の全ての誤りを検出できる。ただし、それ以外の誤りも数多く検出できる。
また、バースト誤り検出能力については、長さが生成多項式Ｇ（ｘ）の次数以下の誤りは全て検出できる。ただし、長さが生成多項式の次数よりも大きいバースト誤りであっても、その多くは検出可能である。
【００２７】
非特許文献２〜８において、符号の未検出誤り確率を最小化する生成多項式に関する様々な報告がなされており、生成多項式の次数（パリティ数）や符号長に応じて様々なものが提案されている。
非特許文献２、３では、１６ビットＣＲＣにおいて、各符号長に対して符号の未検出誤り確率が最小となるような生成多項式を提案している。
また、非特許文献５、８において、符号の未検出誤り確率Ｐudは、符号長ｎが変化すると、符号の最小ハミング距離d minの変化する符号長を境に極端に上昇する特性を示すことが確認されている。
【００２８】
図７は、８ビットＣＲＣの場合の最小（限界）未検出誤り確率特性を例にとって示したグラフである。図７において、横軸は符号長ｎ（ビット）を示し、縦軸は符号の未検出誤り確率Ｐudを示す。これをｎ−Ｐud特性という。
【００２９】
特許文献１には、ＣＲＣ生成多項式の選択方法に関する発明が開示されている。
特許文献１において、生成多項式の次数が与えられたとき、その次数の全ての生成多項式に対して計算したdistance spectrum（距離スペクトル）を元に生成多項式を選択する。このdistance spectrumは、それぞれのハミング距離における符号語の数を表したテーブルである。これにより、最大・最小ハミング距離を持った生成多項式を選択し、符号の未検出誤り確率を最小化する生成多項式を選択する。
【００３０】
【非特許文献１】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.
【特許文献１】J. M. Stein, “METHOD FOR SELECTING CYCLIC REDUNDANCY CHECK POLYNOMIALS FOR LINEAR CODED SYSTEMS”, US Patent 6,085,349, Qualcomm Incorporated, Filed Aug. 27, 1997.
【発明の開示】
【発明が解決しようとする課題】
【００３１】
上述したように、ＣＲＣの誤り検出能力（符号の未検出誤り確率、ランダム誤り検出能力、バースト誤り検出能力）は、生成多項式と符号長によって決まる。
全ての符号長において符号の未検出誤り確率が最小（限界値）となる生成多項式や符号の最小ハミング距離が最大となる生成多項式は存在せず、符号長に応じて符号の未検出誤り確率が最小もしくは符号の最小ハミング距離が最大となる生成多項式は異なる。
つまり、広く用いられているＣＣＩＴＴ規格やＡＮＳＩ規格、および、非特許文献４〜８に示される生成多項式などは、符号の未検出誤り確率が最小、符号の最小ハミング距離が最大となる符号長の範囲は限られている。
【００３２】
上述した文献の多くは、データ通信などにおける符号長の長い（数千ビット以上の）場合に符号の未検出誤り確率が最小（限界値）となるように設計されており、ヘッダ情報に対してＣＲＣを用いる場合や、光ディスクなどの記録媒体へのデータの記録にＣＲＣを用いる場合など、符号長のより短い場合においては、更に良い性能を示すものが存在するはずであるが、提案されていない。
【００３３】
非特許文献２、３などでは、符号長ごとに符号の未検出誤り確率が最も低い生成多項式の提案をしているが、この場合、異なる符号長において用いる場合には、その都度異なる生成多項式を用いなければならなかった。
たとえば、特許文献１では、符号長ごとに符号の最小ハミング距離が最大値を持つ生成多項式を選択しているが、これは回路規模の増加につながるという問題があった。
【００３４】
実際のシステムにおいては、様々な符号長やパリティ長のものが使用されるが、これまで、全ての符号長やパリティ長について最適なＣＲＣ符号が明らかとなっている訳ではなく、現在知られているＣＲＣ符号だけでは、実際のシステムにおいて最小の未検出誤り確率Ｐudを得る上で、必ずしも十分ではなかった。
【００３５】
以上から、与えられた符号長およびパリティ長において符号の未検出誤り確率ができるだけ低く、符号の最小ハミング距離が出来るだけ大きく、かつ、出来るだけ広い符号長範囲において使用できる生成多項式が望まれている。
さらに、たとえば、図１の送信装置１に用いるＣＲＣ符号器、受信装置３に用いるＣＲＣ検出器を回路として装置化する際には、できるだけその回路が簡略化できるＣＲＣ符号化方式が望まれる。
【００３６】
本発明の目的は、与えられた符号長およびパリティ長において符号の未検出誤り確率ができるだけ低く、符号の最小ハミング距離が出来るだけ大きく、かつ、出来るだけ広い符号長範囲において使用できる生成多項式を選択する、ＣＲＣ生成多項式の選択方法を提供することにある。
本発明のさらなる目的は、上記ＣＲＣ生成多項式の選択方法で選択した、生成多項式を抽出して、ＣＲＣ符号器、ＣＲＣ検出器などに適用可能にすることにある。
本発明の目的は、そのようにして、ＣＲＣ符号器、ＣＲＣ検出器などを具体的に構成して提供することにある。
【課題を解決するための手段】
【００３７】
本発明によれば、ＣＲＣ符号および／またはＣＲＣ符号結果をＣＲＣ検査するために用いる生成多項式を選択する方法であって、ｋビットの情報語を持ち、該情報語についてｒビットのパリティが付加された符号長（ｎ）の符号の各符号長（ｎ）における最小ハミング距離（d min）の最大値である最大・最小ハミング距離（Ｍａｘ．d min）を求める第１工程と、最大・最小ハミング距離（Ｍａｘ．d min）の変化する符号長（ｎ）を求め、その符号長ｎの範囲（ｎmin （ｒ，Ｍａｘ．d min ）≦ｎ≦ｎmax （ｒ，Ｍａｘ．d min ））を求める第２工程と、前記符号長（ｎ）の範囲（ｎmin （ｒ，Ｍａｘ．d min ）≦ｎ≦ｎmax （ｒ，Ｍａｘ．d min ））において、常に、符号の最小ハミング距離（d min ）が最大・最小ハミング距離（Ｍａｘ．d min ）と等しい条件（d min ＝Ｍａｘ．d min ）を満たす生成多項式（Ｇ（ｘ））を全検索によって見いだす第３工程と、前記全検索によって見いだした生成多項式（Ｇ（ｘ））の中から、項数（ｗ）、符号の未検出誤り確率（Ｐud）も最小のものを選び出す第４工程とを備えたＣＲＣ生成多項式の選択方法が提供される。
【００３８】
好ましくは、前記第３および第４工程は、周期（ｐ）が最大符号長（ｎmax （ｒ，Ｍａｘ．d min ））以上であり（ｐ≧ｎmax （ｒ，Ｍａｘ．d min ））、かつ、（ｎmax ，ｎmax −ｒ）の符号について最小ハミング距離（d min ）が最大・最小ハミング距離（Ｍａｘ．d min ）と等しい条件（d min ＝Ｍａｘ．d min ）を満たす生成多項式Ｇ（ｘ）を全検索により見付ける工程と、前記全検索により見いだした生成多項式（Ｇ（ｘ））の中から、項数（ｗ）が最小の生成多項式（Ｇ（ｘ））を選ぶ工程と、前記選択した生成多項式（Ｇ（ｘ））について、符号の未検出誤り確率（Ｐud）が最小になる生成多項式（Ｇ（ｘ））を見いだす工程と、を有する。
【００３９】
また好ましくは、前記生成多項式Ｇ（ｘ）を検索および選択する工程において、最大・最小ハミング距離（Ｍａｘ．d min ）がＭａｘ．d min ＝２については、周期（ｐ）が最大周期２r −１をもつ（原始多項式である）生成多項式Ｇ（ｘ）の中で、生成多項式の項数ｗ、および、符号の未検出誤り確率Ｐudが最小である生成多項式Ｇ（ｘ）を選択する。
【００４０】
上記ＣＲＣ生成多項式の選択方法により、下記のいずれかの生成多項式Ｇ（ｘ）が選択される。
１．ｒ＝３、ｎ＝４のとき、生成多項式Ｇ（ｘ）＝ｘ3＋ｘ2＋ｘ＋１である、
２．ｒ＝６、ｎ＝７のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である、
３．ｒ＝６、ｎ＝８のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ4＋ｘ2＋ｘ＋１（相反多項式：ｘ6＋ｘ5＋ｘ4＋ｘ2＋１）である、
４．ｒ＝６、ｎ＝８のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ4＋ｘ3＋ｘ＋１（相反多項式：ｘ6＋ｘ5＋ｘ3＋ｘ2＋１）である、
５．ｒ＝６、ｎ＝８のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ5＋ｘ3＋ｘ＋１である、
６．ｒ＝８、ｎ＝９のとき、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である、
７．ｒ＝１０、ｎ＝１１のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である、
８．ｒ＝１０、ｎ＝１２のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ8＋ｘ6＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ4＋ｘ2＋１）である、
９．ｒ＝１２、ｎ＝１３のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である、
１０．ｒ＝１２、ｎ＝１４のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ10＋ｘ8＋ｘ6＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ8＋ｘ6＋ｘ4＋ｘ2＋１）である、
１１．ｒ＝１４、ｎ＝１５のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である、
１２．ｒ＝１４、ｎ＝１６のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ12＋ｘ10＋ｘ9＋ｘ7＋ｘ5＋ｘ4＋ｘ3＋ｘ＋１（相反多項式：ｘ14＋ｘ13＋ｘ11＋ｘ10＋ｘ9＋ｘ7＋ｘ5＋ｘ4＋ｘ2＋１）である、
１３．ｒ＝１４、ｎ＝１７のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ11＋ｘ8＋ｘ6＋ｘ5＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ9＋ｘ8＋ｘ6＋ｘ3＋１）である、
１４．ｒ＝１６、ｎ＝１７のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ15＋ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である、
１５．ｒ＝１６、ｎ＝１８のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ14＋ｘ12＋ｘ10＋ｘ8＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ16＋ｘ15＋ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ10＋ｘ8＋ｘ6＋ｘ4＋ｘ2＋１）である、
１６．ｒ＝１６、ｎ＝２２のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ8＋ｘ7＋ｘ6＋ｘ4＋ｘ2＋ｘ＋１（相反多項式：ｘ16＋ｘ15＋ｘ14＋ｘ12＋ｘ10＋ｘ9＋ｘ8＋ｘ3＋１）である。
【００４１】
また上記ＣＲＣ生成多項式の選択方法により、下記のいずれかの生成多項式Ｇ（ｘ）が選択される。
１．ｒ＝４、６≦ｎ≦７のとき、生成多項式Ｇ（ｘ）＝ｘ4＋ｘ2＋ｘ＋１（相反多項式：ｘ4＋ｘ3＋ｘ2＋１）である、
２．ｒ＝６、９≦ｎ≦３１のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ2＋ｘ＋１（相反多項式：ｘ6＋ｘ5＋ｘ4＋１）である、
３．ｒ＝８、１０≦ｎ≦１２のとき、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ5＋ｘ4＋ｘ3＋ｘ＋１（相反多項式：ｘ8＋ｘ7＋ｘ5＋ｘ4＋ｘ3＋１）である、
４．ｒ＝８、１０≦ｎ≦１２のとき、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ6＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ2＋１）である、
５．ｒ＝８、１８≦ｎ≦１２７のとき、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ4＋ｘ＋１（相反多項式：ｘ8＋ｘ7＋ｘ4＋１）である、
６．ｒ＝８、ｎ≧１２８のとき、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ5＋ｘ3＋ｘ2＋１（相反多項式：ｘ8＋ｘ6＋ｘ5＋ｘ3＋１）である、
７．ｒ＝１０、２３≦ｎ≦３１のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ9＋ｘ3＋ｘ＋１（相反多項式：ｘ10＋ｘ9＋ｘ7＋ｘ＋１）である、
８．ｒ＝１０、３２≦ｎ≦５１１のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ5＋ｘ2＋１（相反多項式：ｘ10＋ｘ8＋ｘ5＋１）である、
９．ｒ＝１０、ｎ≧５１２のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ3＋１（相反多項式：ｘ10＋ｘ7＋１）である、
１０．ｒ＝１２、２４≦ｎ≦３９のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ11＋ｘ7＋ｘ3＋ｘ＋１（相反多項式：ｘ12＋ｘ11＋ｘ9＋ｘ5＋ｘ＋１）である、
１１．ｒ＝１２、４０≦ｎ≦６５のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ10＋ｘ7＋ｘ6＋ｘ5＋ｘ2＋１である、
１２．ｒ＝１２、６６≦ｎ≦２０４７のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ7＋ｘ2＋１（相反多項式：ｘ12＋ｘ10＋ｘ5＋１）である、
１３．ｒ＝１２、ｎ≧２０４８のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ7＋ｘ6＋ｘ4＋１（相反多項式：ｘ12＋ｘ8＋ｘ6＋ｘ5＋１）である、
１４．ｒ＝１４、２８≦ｎ≦７１のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ10＋ｘ9＋ｘ6＋ｘ2＋１（相反多項式：ｘ14＋ｘ12＋ｘ8＋ｘ5＋ｘ4＋１）である、
１５．ｒ＝１４、７２≦ｎ≦１２７のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ11＋ｘ5＋ｘ3＋１（相反多項式：ｘ14＋ｘ11＋ｘ9＋ｘ3＋１）である、
１６．ｒ＝１４、１２８≦ｎ≦８１９１のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ5＋ｘ2＋１（相反多項式：ｘ14＋ｘ12＋ｘ9＋１）である、
１７．ｒ＝１４、ｎ≧８１９２のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ6＋ｘ4＋ｘ＋１（相反多項式：ｘ14＋ｘ13＋ｘ10＋ｘ8＋１）である、
１８．ｒ＝１６、１９≦ｎ≦２１のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ12＋ｘ9＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ2＋１（相反多項式：ｘ16＋ｘ14＋ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ7＋ｘ4＋ｘ3＋１）である、
１９．ｒ＝１６、１９≦ｎ≦２１のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ12＋ｘ9＋ｘ7＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋１（相反多項式：ｘ16＋ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ9＋ｘ7＋ｘ4＋ｘ3＋１）である、
２０．ｒ＝１６、２３≦ｎ≦３１のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ11＋ｘ5＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ16＋ｘ15＋ｘ14＋ｘ13＋ｘ11＋ｘ5＋ｘ3＋１）である、
２１．ｒ＝１６、３６≦ｎ≦１５１のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ15＋ｘ13＋ｘ8＋ｘ5＋ｘ3＋ｘ＋１（相反多項式：ｘ16＋ｘ15＋ｘ13＋ｘ11＋ｘ8＋ｘ3＋ｘ＋１）である、
２２．ｒ＝１６、１５２≦ｎ≦２５７のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ15＋ｘ8＋ｘ＋１である、
２３．ｒ＝１６、２５８≦ｎ≦３２７６７のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ2＋１（相反多項式：ｘ16＋ｘ14＋ｘ3＋１）である、
２４．ｒ＝１６、ｎ≧３２７６８のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ9＋ｘ7＋ｘ4＋１（相反多項式：ｘ16＋ｘ12＋ｘ9＋ｘ7＋１）である。
【００４２】
本発明によれば、上記選択された生成多項式Ｇ（ｘ）を用いたＣＲＣ符号化を行う、ＣＲＣ符号化方法が提供される。
【００４３】
また本発明によれば、上記選択された生成多項式Ｇ（ｘ）を、シフトレジスタと前記生成多項式Ｇ（ｘ）の係数に応じて設けられた排他的論理和回路と巡回的に接続し、かつ、前記生成多項式Ｇ（ｘ）の係数に応じて設けられた排他的論理和回路に、最終段の排他的論理和回路の出力を入力する回路構成を持つ、ＣＲＣ符号化回路が提供される。
【００４４】
本発明によれば、次数（パリティ数）ｒ、周期ｐの生成多項式Ｇ（ｘ）を用いて符号長ｎのＣＲＣ符号の符号化を行うＣＲＣ符号化方法であって、符号長ｎおよび次数ｒによって規定されるＣＲＣ符号の最小ハミング距離最大値Ｍａｘ．d min 、次数ｒのもとで符号の最小ハミング距離最大値Ｍａｘ．d min が一定となる符号長ｎの範囲をｎmin ≦ｎ≦ｎmax としたとき（ただし、ｎmin は最小符号長であり、ｎmax は最大符号長である）、周期ｐ≧最大符号長ｎmax 、もしくは、周期ｐ＝２r −１、かつ、ｎmin ≦ｎ≦ｎmax の条件下において、符号の最小ハミング距離d min がd min ＝Ｍａｘ．d min を満たす生成多項式Ｇ（ｘ）のなかで、生成多項式Ｇ（ｘ）の項数が最小となり、かつ、２次元対称通信路における符号の未検出誤り確率が最小となる生成多項式Ｇ（ｘ）を用いる、ＣＲＣ符号化方法が提供される。
【発明の効果】
【００４５】
本発明による、生成多項式を用いて生成されるＣＲＣ符号化方式を用いることで、従来から広く用いられている生成多項式を用いる場合に比べ、所望のパリティビットおよび符号長において、符号の未検出誤り確率を低く抑えることが出来、かつ、符号の最小ハミング距離が最大値をとることで、ランダム誤り検出能力を最大にすることが出来る。
【００４６】
さらに、生成多項式Ｇ（ｘ）はｎmin （ｒ、Ｍａｘ．d min ）≦ｎ≦ｎmax （ｒ，Ｍａｘ．d min ）の符号長範囲において符号の最小ハミング距離d minがd min＝Ｍａｘ．d minを満たし、かつ符号の未検出誤り確率ＰudがＰud≒（限界値）を満たすので、符号長ｎが変化する場合でも、この符号長範囲内であれば単一の生成多項式で対応することが可能である。
【００４７】
さらに、ｎmin （ｒ、Ｍａｘ．d min ）≦ｎ≦ｎmax （ｒ，Ｍａｘ．d min ）の符号長範囲において、常に、符号の最小ハミング距離（d min ）が最大値をとる生成多項式Ｇ（ｘ）の中で、最小の項数ｗのものを用いているので、回路に実装するときの回路規模も少なくて済む。
【００４８】
また、符号長ｎと符号の未検出誤り確率Ｐudが決まれば、それを満たすために必要なパリティ数（次数ｒ）が分かるので、そのパリティ数ｒ、符号長ｎにおいて選択された生成多項式Ｇ（ｘ）を用いることで、所望の未検出誤り確率を実現することが出来る。
【発明を実施するための最良の形態】
【００４９】
ＣＲＣ符号選択方法
本発明の発明者は、図７に例示したように、符号の最小ハミング距離d min の変化する符号長ｎを境に符号の未検出誤り確率Ｐudの特性が急激に劣化することに着目した。図７のｎ−Ｐud特性は、各符号長における種々の生成多項式Ｇ（ｘ）についての限界を示している。
８ビットＣＲＣについての図７の例示において、符号長ｎ＝１０〜１２、１３〜１７、１８〜１２７、１２８〜２５５などの境界で符号の未検出誤り確率Ｐudが急激に変化する。
【００５０】
また、符号の最小ハミング距離d min の変化する上記符号長ｎは生成多項式によって異なる。
さらに、符号長ｎにおける符号の最小ハミング距離d min は生成多項式によって異なる。
【００５１】
図８は本発明のＣＲＣ符号選択方法の処理内容の１例を示すフローチャートである。
以下、上述した認識の元、図８を参照して、本発明の発明者による本発明のＣＲＣ符号選択方法について述べる。
【００５２】
ステップ１：Ｍａｘ．d min を求める。
符号の最小ハミング距離d min は、大きい程、ランダム誤り検出能力が高く、符号の未検出誤り確率が低いため、望ましいので、まず、パリティ数（次数）ｒの符号の各符号長における最小ハミング距離d min の最大値（これを最大・最小ハミング距離、または、最小ハミング距離・最大値といい、Ｍａｘ．d min で表す）を求める。
【００５３】
ステップ２：Ｍａｘ．d min の変化する符号長ｎを求める。
次いで、最大・最小ハミング距離Ｍａｘ．d min の変化する符号長ｎを求め、Ｍａｘ．d minが一定の符号長ｎの範囲をｎmin （ｒ，Ｍａｘ．d min ）≦ｎ≦ｎmax （ｒ，Ｍａｘ．d min ）と表す。ｎmin （ｒ，Ｍａｘ．d min ）は、符号長ｎの最小範囲ｎmin が、ｒとＭａｘ．d min で規定されることを意味しており、同様に、符号長ｎの最大範囲ｎmax が、ｒとＭａｘ．d min とで規定されることを示している。
【００５４】
８ビットＣＲＣの場合を図７に例示する。
ただし、符号長ｎが生成多項式Ｇ（ｘ）の周期ｐを超えると、図７の例では、ｎ≧２５６になると、符号の最小ハミング距離d min は必ず２となる。
生成多項式Ｇ（ｘ）の周期ｐは、生成多項式Ｇ（ｘ）が原始多項式のとき最大となり、その最大周期は（２r - １）で表される。つまり、Ｍａｘ．d min ＝２における符号長ｎの範囲は、生成多項式Ｇ（ｘ）に関わらず必ず２r≦ｎ≦∞となる。すなわち、ｎmin （ｒ，２）＝２r、ｎmax （ｒ，２）＝∞となる。
【００５５】
ステップ３：ｎmin ≦ｎ≦ｎmax において、常に、d min ＝Ｍａｘ．d min を満たすＧ（ｘ）を全検索によって見いだす。
次に、出来るだけ広い範囲の符号長ｎにおいて使用できる生成多項式が望ましいので、ｎmin （ｒ，Ｍａｘ．d min ）≦ｎ≦ｎmax （ｒ，Ｍａｘ．d min ）において、常に、d min ＝Ｍａｘ．d min を満たす生成多項式Ｇ（ｘ）を全検索によって見いだす。
【００５６】
ステップ４：全検索によって見いだしたＧ（ｘ）の中から、項数ｗ、符号の未検出誤り確率Ｐudも最小のものを選び出す。
さらに、全検索によって見いだした生成多項式Ｇ（ｘ）の中から、項数ｗ、符号の未検出誤り確率Ｐudも最小のものを選び出す。
【００５７】
ステップ３および４における検索および選択の方法について、図９を参照して、具体例を述べる。
【００５８】
ステップ４１：ｐ≧ｎmax を満たし、かつ、（ｎmax ，ｎmax −ｒ）の符号についてd min ＝Ｍａｘ．d min を満たすＧ（ｘ）を全検索により見付ける。
まず、ｎmin （ｒ，Ｍａｘ．d min ）≦ｎ≦ｎmax （ｒ，Ｍａｘ．d min ）において常に、d min ＝Ｍａｘ．d min を満たすためには、周期ｐについてｐ≧ｎmax （ｒ，Ｍａｘ．d min ）を満たし、かつ、（ｎmax ，ｎmax −ｒ）の符号についてd min ＝Ｍａｘ．d min を満たす必要があるので、この条件を満たす生成多項式Ｇ（ｘ）を全検索により見付ける。
【００５９】
ステップ４２：全検索により見いだしたＧ（ｘ）の中から、項数ｗが最小の生成多項式Ｇ（ｘ）を選ぶ。
次に、全検索により見いだした生成多項式Ｇ（ｘ）の中から、項数ｗが最小の生成多項式Ｇ（ｘ）を選ぶ。また、Ｇ（ｘ）の項数がｗのとき、Ｇ（ｘ）によって生成された符号語には、ハミング距離d Hがｗとなる符号語が必ず存在する。したがって、Ｇ（ｘ）によって生成される符号の最小ハミング距離d minが最大・最小ハミング距離Ｍａｘ．d minとなっているならば、必ずｗ≧Ｍａｘ．d minである。このことを利用して、ステップ４１において検索するＧ（ｘ）の中でｗ＜Ｍａｘ．d minのものは省略することが可能である。
【００６０】
ステップ４３：Ｐudが最小になるＧ（ｘ）を見いだす。
次に、この生成多項式Ｇ（ｘ）を用いて符号化したＣＲＣ符号のｎmin （ｒ，Ｍａｘ．d min ）≦ｎ≦ｎmax （ｒ，Ｍａｘ．d min ）における、符号の未検出誤り確率Ｐudを式４によって求め、Ｐudが最小となる生成多項式Ｇ（ｘ）を見いだす。
【００６１】
ただし、符号長ｎが大きくなり、Ｍａｘ．d min ＝２の場合については、上述したように、符号長ｎの範囲が２r ≦ｎ≦∞、すなわち、ｎmin （ｒ，２）＝２r 、ｎmax （ｒ，２）＝∞であるので、ステップ４１に示した手順で生成多項式Ｇ（ｘ）を検索することが出来ない。
【００６２】
また、２r ≦ｎにおいて、全ての生成多項式Ｇ（ｘ）はd min ＝Ｍａｘ．d min ＝２を満たす。そこで、d min ＝２のときは周期ｐが大きい程符号の未検出誤り確率Ｐudが低いという性質を利用して、Ｍａｘ．d min ＝２については、周期ｐが最大周期２r −１をもつ（原始多項式である）生成多項式Ｇ（ｘ）の中で、多項式の項数ｗ、符号の未検出誤り確率Ｐudが最小である生成多項式Ｇ（ｘ）を選択する。つまり、これは、Ｍａｘ．d min ＝３で求めた生成多項式Ｇ（ｘ）と一致する。その理由は、ｎmax （ｒ，３）＝２r −１であるからである。
【００６３】
実施例と比較例
以上の方法で見いだした生成多項式Ｇ（ｘ）の例と、比較例を述べる。
表１−Ａ〜表１−Ｃは、パリティビット数（次数）ｒ＝３，４，６，８，１０，１２，１４，１６の各符号長における生成多項式Ｇ（ｘ）の、本発明における実施例と、比較例として、一般的に用いられている生成多項式の例を示したものである。
【００６４】
【表１−Ａ】
2006180172.tif 000005
【００６５】
【表１−Ｂ】
2006180172.tif 000006
【００６６】
【表１−Ｃ】
2006180172.tif 000007
【００６７】
表１−Ａ〜表１−Ｃの１列目は、パリティビット数ｒを表し、２列目、３列目は、それぞれ、符号の最大・最小ハミング距離Ｍａｘ．d min を満たす符号長ｎの範囲と、その最大・最小ハミング距離Ｍａｘ．d min である。
生成多項式Ｇ（ｘ）について、１６進数表記をしている。たとえば、１６進数表記の「Ｆ」は、２進数表記で「１１１１」になる。また、１６進数表記の「１２Ｄ」であれば、２進数で表すと、「１００１０１１０１」であるので、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ5＋ｘ3＋ｘ2＋１を表す。
また、高次の係数と低次の係数を逆転した多項式を相反多項式（reciprocal polynomial）といい、同じ特性を示す。
【００６８】
表１−Ａ〜表１−Ｃの４〜７列目のデータが本発明の実施例における生成多項式を用いて生成した符号の最小ハミング距離d min 、生成多項式Ｇ（ｘ）、項数ｗ、および、符号の未検出誤り確率Ｐudを表す。
表１−Ａ〜表１−Ｃの８〜１１列目のデータが比較例における生成多項式を用いて生成した符号の最小ハミング距離d min 、生成多項式Ｇ（ｘ）、項数ｗ、および、符号の未検出誤り確率Ｐudを表す。
表１−Ａ〜表１−Ｃにおいて、“−”記号は、上記の検索を行い選択した生成多項式が他文献で既に提案されている部分であり、その部分については、参考までに表２に示す。
【００６９】
【表２】
2006180172.tif 000008
【００７０】
本発明の実施例として示した生成多項式Ｇ（ｘ）は、ｎmin （ｒ，Ｍａｘ．d
min ）≦ｎ≦ｎmax （ｒ，Ｍａｘ．d min ）において、d min ＝Ｍａｘ．d min
を満たし、さらに、その生成多項式Ｇ（ｘ）の中で項数ｗが最小であり、さらに、その中で符号の未検出誤り確率Ｐudが最も低い生成多項式となっている。
【００７１】
さらに、図１０、図１１は、それぞれ、１６ビットＣＲＣ、８ビットＣＲＣにおける符号長ｎと符号の未検出誤り確率Ｐudとの特性（ｎ−Ｐud特性）を示したものである。
この例示において、左から順に生成多項式Ｇ（ｘ）、項数ｗ、Ｍａｘ．d min一定の符号長範囲ｎmin ≦ｎ≦ｎmaxを表し、最後に“new”と示されていれば本発明によるもの、“〔〕”で括られたものはすでに他文献に提案されているものであり、数字はその文献番号を表す。
【００７２】
以上のようにして得た生成多項式Ｇ（ｘ）の例を整理して、下記に列挙する。
【００７３】
（１）次数ｒ＝３、符号長ｎ＝４のとき、生成多項式Ｇ（ｘ）＝ｘ3＋ｘ2＋ｘ＋１である。
（２）次数ｒ＝４、符号長ｎが６≦ｎ≦７のとき、生成多項式Ｇ（ｘ）＝ｘ4＋ｘ2＋ｘ＋１（相反多項式：ｘ4＋ｘ3＋ｘ2＋１）である。
（３）次数ｒ＝６、符号長ｎ＝７のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である。
（４）次数ｒ＝６、符号長ｎ＝８のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ4＋ｘ2＋ｘ＋１（相反多項式：ｘ6＋ｘ5＋ｘ4＋ｘ2＋１）である。
（５）次数ｒ＝６、符号長ｎ＝８のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ4＋ｘ3＋ｘ＋１（相反多項式：ｘ6＋ｘ5＋ｘ3＋ｘ2＋１）である。
（６）次数ｒ＝６、符号長ｎ＝８のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ5＋ｘ3＋ｘ＋１である。
（７）次数ｒ＝６、符号長ｎが９≦ｎ≦３１のとき、生成多項式Ｇ（ｘ）＝ｘ6＋ｘ2＋ｘ＋１（相反多項式：ｘ6＋ｘ5＋ｘ4＋１）である。
（８）次数ｒ＝８、符号長ｎ＝９のとき、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である。
（９）次数ｒ＝８、符号長ｎが１０≦ｎ≦１２のとき、
生成多項式Ｇ（ｘ）＝ｘ8＋ｘ5＋ｘ4＋ｘ3＋ｘ＋１（相反多項式：ｘ8＋ｘ7＋ｘ5＋ｘ4＋ｘ3＋１）である。
（１０）次数ｒ＝８、符号長ｎが１０≦ｎ≦１２のとき、
生成多項式Ｇ（ｘ）＝ｘ8＋ｘ6＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ2＋１）である。
（１１）次数ｒ＝８、符号長ｎが１８≦ｎ≦１２７のとき、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ4＋ｘ＋１（相反多項式：ｘ8＋ｘ7＋ｘ4＋１）である。
（１２）次数ｒ＝８、符号長ｎがｎ≧１２８のとき、生成多項式Ｇ（ｘ）＝ｘ8＋ｘ5＋ｘ3＋ｘ2＋１（相反多項式：ｘ8＋ｘ6＋ｘ5＋ｘ3＋１）である。
（１３）次数ｒ＝１０、符号長ｎがｎ＝１１のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である。
（１４）次数ｒ＝１０、符号長ｎがｎ＝１２のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ8＋ｘ6＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ4＋ｘ2＋１）である。
（１５）次数ｒ＝１０、符号長ｎが２３≦ｎ≦３１のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ9＋ｘ3＋ｘ＋１（相反多項式：ｘ10＋ｘ9＋ｘ7＋ｘ＋１）である。
（１６）次数ｒ＝１０、符号長ｎが３２≦ｎ≦５１１のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ5＋ｘ2＋１（相反多項式：ｘ10＋ｘ8＋ｘ5＋１）である。
（１７）次数ｒ＝１０、符号長ｎがｎ≧５１２のとき、生成多項式Ｇ（ｘ）＝ｘ10＋ｘ3＋１（相反多項式：ｘ10＋ｘ7＋１）である。
（１８）次数ｒ＝１２、符号長ｎがｎ＝１３のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である。
（１９）次数ｒ＝１２、符号長ｎがｎ＝１４のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ10＋ｘ8＋ｘ6＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ8＋ｘ6＋ｘ4＋ｘ2＋１）である。
（２０）次数ｒ＝１２、符号長ｎが２４≦ｎ≦３９のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ11＋ｘ7＋ｘ3＋ｘ＋１（相反多項式：ｘ12＋ｘ11＋ｘ9＋ｘ5＋ｘ＋１）である。
（２１）次数ｒ＝１２、符号長ｎが４０≦ｎ≦６５のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ10＋ｘ7＋ｘ6＋ｘ5＋ｘ2＋１である。
（２２）次数ｒ＝１２、符号長ｎが６６≦ｎ≦２０４７のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ7＋ｘ2＋１（相反多項式：ｘ12＋ｘ10＋ｘ5＋１）である。
（２３）次数ｒ＝１２、符号長ｎがｎ≧２０４８のとき、生成多項式Ｇ（ｘ）＝ｘ12＋ｘ7＋ｘ6＋ｘ4＋１（相反多項式：ｘ12＋ｘ8＋ｘ6＋ｘ5＋１）である。
（２４）次数ｒ＝１４、符号長ｎがｎ＝１５のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である。
（２５）次数ｒ＝１４、符号長ｎがｎ＝１６のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ12＋ｘ10＋ｘ9＋ｘ7＋ｘ5＋ｘ4＋ｘ3＋ｘ＋１（相反多項式：ｘ14＋ｘ13＋ｘ11＋ｘ10＋ｘ9＋ｘ7＋ｘ5＋ｘ4＋ｘ2＋１）である。
（２６）次数ｒ＝１４、符号長ｎがｎ＝１７のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ11＋ｘ8＋ｘ6＋ｘ5＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ9＋ｘ8＋ｘ6＋ｘ3＋１）である。
（２７）次数ｒ＝１４、符号長ｎが２８≦ｎ≦７１のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ10＋ｘ9＋ｘ6＋ｘ2＋１（相反多項式：ｘ14＋ｘ12＋ｘ8＋ｘ5＋ｘ4＋１）である。
（２８）次数ｒ＝１４、符号長ｎが７２≦ｎ≦１２７のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ11＋ｘ5＋ｘ3＋１（相反多項式：ｘ14＋ｘ11＋ｘ9＋ｘ3＋１）である。
（２９）次数ｒ＝１４、符号長ｎが１２８≦ｎ≦８１９１のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ5＋ｘ2＋１（相反多項式：ｘ14＋ｘ12＋ｘ9＋１）である。
（３０）次数ｒ＝１４、符号長ｎがｎ≧８１９２のとき、生成多項式Ｇ（ｘ）＝ｘ14＋ｘ6＋ｘ4＋ｘ＋１（相反多項式：ｘ14＋ｘ13＋ｘ10＋ｘ8＋１）である。
（３１）次数ｒ＝１６、符号長ｎがｎ＝１７のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ15＋ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ8＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１である。
（３２）次数ｒ＝１６、符号長ｎがｎ＝１８のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ14＋ｘ12＋ｘ10＋ｘ8＋ｘ6＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ16＋ｘ15＋ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ10＋ｘ8＋ｘ6＋ｘ4＋ｘ2＋１）である。
（３３）次数ｒ＝１６、符号長ｎが１９≦ｎ≦２１のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ12＋ｘ9＋ｘ7＋ｘ6＋ｘ5＋ｘ4＋ｘ2＋１（相反多項式：ｘ16＋ｘ14＋ｘ12＋ｘ11＋ｘ10＋ｘ9＋ｘ7＋ｘ4＋ｘ3＋１）である。
（３４）次数ｒ＝１６、符号長ｎが１９≦ｎ≦２１のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ12＋ｘ9＋ｘ7＋ｘ5＋ｘ4＋ｘ3＋ｘ2＋１（相反多項式：ｘ16＋ｘ14＋ｘ13＋ｘ12＋ｘ11＋ｘ9＋ｘ7＋ｘ4＋ｘ3＋１）である。
（３５）次数ｒ＝１６、符号長ｎがｎ＝２２のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ8＋ｘ7＋ｘ6＋ｘ4＋ｘ2＋ｘ＋１（相反多項式：ｘ16＋ｘ15＋ｘ14＋ｘ12＋ｘ10＋ｘ9＋ｘ8＋ｘ3＋１）である。
（３６）次数ｒ＝１６、符号長ｎが２３≦ｎ≦３１のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ11＋ｘ5＋ｘ3＋ｘ2＋ｘ＋１（相反多項式：ｘ16＋ｘ15＋ｘ14＋ｘ13＋ｘ11＋ｘ5＋ｘ3＋１）である。
（３７）次数ｒ＝１６、符号長ｎが３６≦ｎ≦１５１のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ15＋ｘ13＋ｘ8＋ｘ5＋ｘ3＋ｘ＋１（相反多項式：ｘ16＋ｘ15＋ｘ13＋ｘ11＋ｘ8＋ｘ3＋ｘ＋１）である。
（３８）次数ｒ＝１６、符号長ｎが１５２≦ｎ≦２５７のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ15＋ｘ8＋ｘ＋１である。
（３９）次数ｒ＝１６、符号長ｎが２５８≦ｎ≦３２７６７のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ13＋ｘ2＋１（相反多項式：ｘ16＋ｘ14＋ｘ3＋１）である。
（４０）次数ｒ＝１６、符号長ｎがｎ≧３２７６８のとき、生成多項式Ｇ（ｘ）＝ｘ16＋ｘ9＋ｘ7＋ｘ4＋１（相反多項式：ｘ16＋ｘ12＋ｘ9＋ｘ7＋１）である。
【００７４】
以上のごとく、本発明の実施の形態によれば、種々の条件に則した生成多項式Ｇ（ｘ）を求めることができた。
なお、上記列挙した生成多項式Ｇ（ｘ）について、符号長ｎがｎmin ＝ｎmaxの場合と、ｎmin ≠ｎmax の場合とに２分割して整理することもできる。
【００７５】
ＣＲＣ符号化方法およびＣＲＣ符号化回路
上述した生成多項式Ｇ（ｘ）を、たとえば、図２に示したＣＲＣパリティ生成器１１０、または、図５に示したＣＲＣパリティ検査器３４１に適用できる。
たとえば、図２に示したＣＲＣパリティ生成器１１０について、図３または図４に回路構成を示したように、生成多項式Ｇ（ｘ）の次数に応じて設けられるシフトレジスタと排他的論理和回路を巡回的に接続する。排他的論理和回路は生成多項式Ｇ（ｘ）の係数に応じて設け、最終段の排他的論理和回路、たとえば、図３の第２排他的論理和回路ＥＸＯＲ２の出力を、前段に位置する他の排他的論理和回路に入力する回路構成とする。
このように、生成多項式Ｇ（ｘ）が上述のように求められると、シフトレジスタと排他的論理和回路とを用いて、ＣＲＣ符号化回路を容易に構成することができる。
ＣＲＣパリティ検査器３４１についても同様である。
【００７６】
表１−Ａ〜１−Ｃや、図１０、図１１の例示から理解されるように、これまで広く用いられている比較例の生成多項式は、ある符号長範囲においては、限界値（Bound）に近接した特性を示すが、それ以外の部分においては、符号の最小ハミング距離（d min）・未検出誤り確率（Ｐud）特性において、限界値と比べて大きく劣化する。
それと比較すると、本発明による選択方法に基づく実施例においては、全ての符号長ｎにおいて限界値に近接した特性が得られる。
【００７７】
このように、本発明の好適な実施の形態による、生成多項式を用いて生成されるＣＲＣ符号化方式を用いることで、従来から広く用いられている生成多項式を用いる場合に比べ、所望のパリティビットおよび符号長において、符号の未検出誤り確率を低く抑えることが出来、かつ、符号の最小ハミング距離が最大値をとることで、ランダム誤り検出能力を最大にすることが出来る。
【００７８】
さらに、ｎmin （ｒ、Ｍａｘ．d min ）≦ｎ≦ｎmax （ｒ，Ｍａｘ．d min）の符号長範囲において生成多項式Ｇ（ｘ）がd min＝Ｍａｘ．d minかつＰud≒限界値（Bound）を満たしているので、符号長ｎが変化する場合でも、この符号長範囲内であれば単一の生成多項式で対応することが可能である。
【００７９】
さらに、ｎmin （ｒ、Ｍａｘ．d min）≦ｎ≦ｎmax （ｒ，Ｍａｘ．d min）の符号長範囲において、常に、符号の最小ハミング距離（d min）が最大値をとる生成多項式Ｇ（ｘ）の中で、最小の項数ｗのものを用いているので、回路に実装するときの回路規模も少なくて済む。
【００８０】
また、符号長ｎと符号の未検出誤り確率Ｐudが決まれば、それを満たすために必要なパリティ数（次数ｒ）が分かるので、そのパリティ数ｒ、符号長ｎにおいて選択された生成多項式Ｇ（ｘ）を用いることで、所望の未検出誤り確率を実現することが出来る。
【図面の簡単な説明】
【００８１】
【図１】図１は本発明のＣＲＣ符号化方法およびＣＲＣ符号化装置が適用される１例としての、送信装置および受信装置の構成の例を示す図である。
【図２】図２は図１の送信装置におけるＣＲＣ符号器の構成例を示す図である。
【図３】図３は図２に図解したＣＲＣ符号器におけるＣＲＣパリティ生成器の第１構成例を示す図である。
【図４】図４は図２に図解したＣＲＣ符号器におけるＣＲＣパリティ生成器の第２構成例を示す図である。
【図５】図５は図１の受信装置におけるＣＲＣ検出器の構成例を示す図である。
【図６】図６は図５に図解したＣＲＣ検出器を構成するＣＲＣパリティ検査器の構成例を示す図である。
【図７】図７は８ビットＣＲＣの場合の符号の最小ハミング距離最大値Ｍａｘ．d min が変化する符号長ｎ（横軸）における符号の未検出誤り確率Ｐud（縦軸）の変化を示すｎ−Ｐud特性を示すグラフである。
【図８】図８は本発明のＣＲＣ符号選択方法の処理内容の１例を示すフローチャートである。
【図９】図９は図８に図解したフローチャートにおける部分詳細処理を示すフローチャートである。
【図１０】図１０は１６ビットＣＲＣにおける本発明の実施例と比較例について、ｎ−Ｐud特性を示すグラフである。
【図１１】図１１は８ビットＣＲＣにおける本発明の実施例と比較例について、ｎ−Ｐud特性を示すグラフである。
【符号の説明】
【００８２】
１…送信装置
１１…ＣＲＣ符号器
１１０…ＣＲＣパリティ生成器、１１１…第１セレクタ
１１２…第２セレクタ、１１３…ビット数カウンタ
１２…誤り訂正符号器、１３…伝送路符号器
２…伝送路
３…受信装置
３１…符号検出器、３２…伝送路復号器、３３…誤り訂正復号器
３４…ＣＲＣ検出器
３４１…ＣＲＣパリティ検査器、３４２…比較器
【図１】
2006180172.tif 000009
【図２】
2006180172.tif 000010
【図３】
2006180172.tif 000011
【図４】
2006180172.tif 000012
【図５】
2006180172.tif 000013
【図６】
2006180172.tif 000014
【図７】
2006180172.tif 000015
【図８】
2006180172.tif 000016
【図９】
2006180172.tif 000017
【図１０】
2006180172.tif 000018
【図１１】
2006180172.tif 000019