(57)【要約】【課題】大きなビット数の入力データであっても少ないクロック数で高速にＣＲＣ符号を生成する。【解決手段】１６ビットの並列入力データを７次の既約多項式で除算してその余りを並列８ビットのＣＲＣ符号としてそれぞれ出力する２個の単位演算回路１０Ｃと、該２個の単位演算回路１０Ｃから出力する合計１６ビットのＣＲＣ符号を７次の既約多項式で除算してその余りを並列８ビットのＣＲＣ符号として出力する１個の単位演算回路１０Ｄと、該１個の単位演算回路１０Ｄから出力する並列８ビットのＣＲＣ符号を保持するレジスタ２０とを備える。【選択図】図２
2014165892.tif 000002
【特許請求の範囲】
【請求項１】
ｍ１ビット（ｍ１は３以上の整数）の圧縮対象データが入力データとして並列に入力され、ｎ１次（ｎ１は２以上でｍ１より小さい整数）の既約多項式を利用して前記入力データを圧縮したｎ１ビットのＣＲＣ符号を並列に出力する第１階層単位演算回路を、複数個備え、全体でｍ２ビット（ｍ２は３以上の整数）の第１階層出力データを並列に出力する第１階層の演算回路と、
前記ｍ２ビットの第１階層出力データが入力データとして並列に入力され、ｎ２次（ｎ２は２以上でｍ２より小さい整数）の既約多項式を利用して該第１階層出力データを圧縮したｎ２ビットのＣＲＣ符号を並列に出力する第２階層単位演算回路を１個備える、第２階層の演算回路と、
を備えたことを特徴とする階層構造の演算回路。
【請求項２】
クロック信号の第１のエッジで前記入力データを保持して前記第１階層単位演算回路に入力する入力側レジスタと、前記クロック信号の次のエッジで前記第１階層出力データを保持して前記第２階層単位演算回路に入力する中間レジスタと、前記クロック信号のさらに次のエッジで前記ｎ２ビットのＣＲＣ符号を保持する出力側レジスタと、をさらに備えることを特徴とする請求項１記載の階層構造の演算回路。
【請求項３】
前記第１階層単位演算回路および第２の階層単位演算回路のそれぞれが、
０ビット目からｍｉ−１ビット目の入力データのうちのｍｉ−ｎｉ−１ビット目からｍｉ−１ビット目まで（ｉ＝１または２）が入力され、前記既約多項式の０次からｎｉ−１次までのそれぞれの項の係数と前記入力データのｍｉ−１ビット目との積と、前記入力データのｍｉ−ｎｉ−１ビット目からｍｉ−２ビット目までのそれぞれとの排他論理和を、０ビット目からｎｉ−１ビット目までの出力として出力する第１段の演算回路段と、
それぞれが、前段の演算回路段の出力と、前記０ビット目からｍｉ−１ビット目の入力データのうちのｍｉ−ｎｉ−ｋビット目（ｋ＝２〜ｍｉ−ｎｉ）とが入力され、前記既約多項式の０次からｎｉ−１次までのそれぞれの項の係数と前記前段の演算回路段のｎｉ−１ビット目の出力との積と、前記入力データのｍｉ−ｎｉ−ｋビット目および前記前段の演算回路段の出力の０ビット目からｎｉ−２ビット目までのそれぞれとの排他論理和を、０ビット目からｎｉ−１ビット目までの出力として出力する第ｋ段目の演算回路段と、を有し、
ｍｉ−ｎｉ段目の論理回路段の出力の前記０ビット目からｎｉ−１ビット目までを前記ｎｉビットＣＲＣ符号として出力することを特徴とする請求項１または２記載の階層構造の演算回路。
【請求項４】
前記複数の第１階層単位演算回路のすべてのｍ１およびｎ１のそれぞれが互いに等しく、かつ、前記第２階層単位演算回路のｍ２およびｎ２のそれぞれと互いに等しいことを特徴とする請求項１ないし３のいずれかに記載の階層構造の演算回路。
【請求項５】
前記第１階層演算回路が２個の前記１階層単位演算回路を備え、
前記１階層単位演算回路のそれぞれにおいてｍ１＝ｎ１×２であり、前記第２階層単位演算回路においてｍ２＝ｎ２×２であることを特徴とする請求項４記載の階層構造の演算回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多ビットの入力データを既約多項式で除算してその余りをＣＲＣ（Cyclic Redundancy Check)符号として出力するＣＲＣ演算回路に係り、特に全体を階層構造に構成した演算回路に関する。
【背景技術】
【０００２】
ＣＲＣは、データ伝送の途中で発生するビット誤りを検出する方式の１つであり、元の情報を既約多項式（自分以外で割り切れない多項式）で除算した余りを符号とするものである。このＣＲＣは圧縮（情報のビット数を減らす）ために利用できる。例えば、製造した半導体装置のテスト結果の情報を圧縮して出力するために利用できる。具体的には、例えば、１２８ビットのテスト結果を８ビットに圧縮して、ＣＲＣ符号として出力することが行われる。テスト結果に何らかの異常がある場合、この８ビットのＣＲＣ符号が期待値と異なった値になるので、１２８ビットのテスト結果全体に代えて８ビットのＣＲＣ符号を出力して、期待値と比較することにより、異常の有無の判断を行うことができる。
【０００３】
例えば、１２８ビットの入力データを８ビットの既約多項式「Ｘ7＋Ｘ4＋１」で除算して８ビットに圧縮したＣＲＣ符号を出力させるＣＲＣ演算回路は、図４に示すように構成される。ＳＥＬはセレクタ、ＦＦ７１〜ＦＦ７８はシフトレジスタを構成するフリップフロップ、ＸＯＲ７１〜７３は排他的論理和回路である。この回路では、シリアルの入力データ１２８ビット分を入力してシフトさせることにより、８ビットのＣＲＣ符号を生成することができる。これに類似の回路として、特許文献１の第３図に、入力データを既約多項式「Ｘ6＋Ｘ＋１」で除算するＣＲＣ演算回路が記載されている。
【０００４】
また、この特許文献１の第１図には、第３図で行われる処理を低速で実現するための構成が記載されている。これは、６ビットのシリアルデータを６ビットのパラレルデータに変換し、６ビットのＣＲＣ符号を生成するものであり、論理段数２段の演算回路で構成されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開昭６４−７７１６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところが、図４に示したＣＲＣ演算回路は、１２８ビットのデータを処理するために、１２８クロックサイクルを必要とし、処理に時間がかかる問題がある。また、特許文献１の第１図に示されたＣＲＣ演算回路では、段数を２段に少なくできるのは、既約多項式を固定とし、かつ、入力データと同じビット数のＣＲＣ符号を生成するからである。任意の既約多項式の利用を可能にし、かつ、入力データより少ないビット数のＣＲＣ符号を生成するためには、さらなる処理段数が必要となる。また、この従来技術では、連続的に入力されるシリアルデータを処理することを前提としており、処理しやすいビット数毎にパラレルデータに変換して処理するものであり、大きなビット数のデータが並列に入力される場合の処理については記載されていない。
【０００７】
本発明の目的は、大きなビット数の並列入力データであっても少ないクロック数で高速にＣＲＣ符号を生成できるようにした階層構造の演算回路を提供することである。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、請求項１にかかる発明の階層構造の演算回路は、ｍ１ビット（ｍ１は３以上の整数）の圧縮対象データが入力データとして並列に入力され、ｎ１次（ｎ１は２以上でｍ１より小さい整数）の既約多項式を利用して前記入力データを圧縮したｎ１ビットのＣＲＣ符号を並列に出力する第１階層単位演算回路を、複数個備え、全体でｍ２ビット（ｍ２は３以上の整数）の第１階層出力データを並列に出力する第１階層の演算回路と、前記ｍ２ビットの第１階層出力データが入力データとして並列に入力され、ｎ２次（ｎ２は２以上でｍ２より小さい整数）の既約多項式を利用して該第１階層出力データを圧縮したｎ２ビットのＣＲＣ符号を並列に出力する第２階層単位演算回路を１個備える、第２階層の演算回路と、を備えたことを特徴とする。
請求項２にかかる発明は、請求項１記載の階層構造の演算回路において、クロック信号の第１のエッジで前記入力データを保持して前記第１階層単位演算回路に入力する入力側レジスタと、前記クロック信号の次のエッジで前記第１階層出力データを保持して前記第２階層単位演算回路に入力する中間レジスタと、前記クロック信号のさらに次のエッジで前記ｎ２ビットのＣＲＣ符号を保持する出力側レジスタと、をさらに備えることを特徴とする。
請求項３にかかる発明は、請求項１または２記載の階層構造の演算回路において、前記第１階層単位演算回路および第２の階層単位演算回路のそれぞれが、０ビット目からｍｉ−１ビット目の入力データのうちのｍｉ−ｎｉ−１ビット目からｍｉ−１ビット目まで（ｉ＝１または２）が入力され、前記既約多項式の０次からｎｉ−１次までのそれぞれの項の係数と前記入力データのｍｉ−１ビット目との積と、前記入力データのｍｉ−ｎｉ−１ビット目からｍｉ−２ビット目までのそれぞれとの排他論理和を、０ビット目からｎｉ−１ビット目までの出力として出力する第１段の演算回路段と、それぞれが、前段の演算回路段の出力と、前記０ビット目からｍｉ−１ビット目の入力データのうちのｍｉ−ｎｉ−ｋビット目（ｋ＝２〜ｍｉ−ｎｉ）とが入力され、前記既約多項式の０次からｎｉ−１次までのそれぞれの項の係数と前記前段の演算回路段のｎｉ−１ビット目の出力との積と、前記入力データのｍｉ−ｎｉ−ｋビット目および前記前段の演算回路段の出力の０ビット目からｎｉ−２ビット目までのそれぞれとの排他論理和を、０ビット目からｎｉ−１ビット目までの出力として出力する第ｋ段目の演算回路段と、を有し、ｍｉ−ｎｉ段目の論理回路段の出力の前記０ビット目からｎｉ−１ビット目までを前記ｎｉビットＣＲＣ符号として出力することを特徴とする。
請求項４にかかる発明は、請求項１ないし３のいずれかに記載の階層構造の演算回路において、前記複数の第１階層単位演算回路のすべてのｍ１およびｎ１のそれぞれが互いに等しく、かつ、前記第２階層単位演算回路のｍ２およびｎ２のそれぞれと互いに等しいことを特徴とする。
請求項５にかかる発明は、請求項４記載の階層構造の演算回路において、前記第１階層演算回路が２個の前記１階層単位演算回路を備え、前記１階層単位演算回路のそれぞれにおいてｍ１＝ｎ１×２であり、前記第２階層単位演算回路においてｍ２＝ｎ２×２であることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、大きなビット数の並列入力データであっても少ないクロック数で高速にＣＲＣ符号を生成できる。また、任意の既約多項式を入力可能であるので、多種の既約多項式に対応できる。また、同一構成の単位演算回路を複数使用した階層構造とすることができるので、入力ビット数の増大に対して容易に対応することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施例のＣＲＣ演算回路の単位演算回路の回路図である。
【図２】本発明の実施例のＣＲＣ演算回路の回路図である。
【図３】図１の単位演算回路において、既約多項式が「Ｘ7＋Ｘ4＋１」のときの単位演算回路の回路図である。
【図４】既約多項式が「Ｘ7＋Ｘ4＋１」のときの従来のＣＲＣ演算回路の回路図である。
【発明を実施するための形態】
【００１１】
図１に本発明の実施例の階層構造の演算回路の単位演算回路１０を示す。この単位演算回路１０は、１６ビットの入力データを圧縮して８ビットのＣＲＣ符号を出力するＣＲＣ（２４，１６）回路であり、共通クロックの立上りに同期して１６ビットの入力データＤｉｎ[１５：０]を取り込む１６個の入力側レジスタを構成するフリップフロップＦＦ１〜ＦＦ１６と、６４個のアンド回路ＡＮＤ１〜ＡＮＤ６４と、６４個の排他的論理和回路ＸＯＲ１〜ＸＯＲ６４から構成される。
【００１２】
１段目の演算回路１１は、アンド回路ＡＮＤ１〜ＡＮＤ８と排他的論理和回路ＸＯＲ１〜ＸＯＲ８により構成されている。アンド回路ＡＮＤ１〜ＡＮＤ８は、最高次の入力データＤｉｎ[１５]と、８ビットの既約多項式の０次から７次までの項の係数（ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ）とのそれぞれの積を演算する。排他的論理和回路ＸＯＲ１〜ＸＯＲ８は、そのアンド回路ＡＮＤ１〜ＡＮＤ８の出力データと入力データＤｉｎ[７]〜Ｄｉｎ[１４]とのそれぞれの排他的論理和を演算する。
【００１３】
２段目の演算回路１２は、アンド回路ＡＮＤ９〜ＡＮＤ１６と排他的論理和回路ＸＯＲ９〜ＸＯＲ１６により構成されている。アンド回路ＡＮＤ９〜ＡＮＤ１６は、前段の排他的論理和回路ＸＯＲ８の出力データと、８ビットの既約多項式の０次から７次までの項の係数（ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ）とのそれぞれの積を演算する。排他的論理和回路ＸＯＲ９〜ＸＯＲ１６は、そのアンド回路ＡＮＤ９〜ＡＮＤ１６の出力データと入力データＤｉｎ[６]および前段の排他的論理和回路ＸＯＲ１〜ＸＯＲ７とのそれぞれの排他的論理和を演算する。
【００１４】
３段目の演算回路１３は、アンド回路ＡＮＤ１７〜ＡＮＤ２４と排他的論理和回路ＸＯＲ１７〜ＸＯＲ２４により構成されている。アンド回路ＡＮＤ１７〜ＡＮＤ２４は、前段の排他的論理和回路ＸＯＲ１６の出力データと、８ビットの既約多項式の０次から７次までの項の係数（ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ）とのそれぞれの積を演算する。排他的論理和回路ＸＯＲ１７〜ＸＯＲ２４は、そのアンド回路ＡＮＤ１７〜ＡＮＤ２４の出力データと入力データＤｉｎ[５]および前段の排他的論理和回路ＸＯＲ９〜ＸＯＲ１５とのそれぞれの排他的論理和を演算する。
【００１５】
以下、同様に、４段目の演算回路１４はアンド回路ＡＮＤ２５〜ＡＮＤ３２と排他的論理和回路ＸＯＲ２５〜ＸＯＲ３２により構成され、８ビットの既約多項式の０次から７次までの項の係数（ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ）と、入力データＤｉｎ[４]と、３段目の演算回路１３の排他的論理和回路の出力データを入力して、同様の演算を行う。
【００１６】
また、５段目の演算回路１５はアンド回路ＡＮＤ３３〜ＡＮＤ４０と排他的論理和回路ＸＯＲ３３〜ＸＯＲ４０により構成され、８ビットの既約多項式の０次から７次までの項の係数（ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ）と、入力データＤｉｎ[３]と、４段目の演算回路１４の排他的論理和回路の出力データを入力して、同様の演算を行う。
【００１７】
また、６段目の演算回路１６はアンド回路ＡＮＤ４１〜ＡＮＤ４８と排他的論理和回路ＸＯＲ４１〜ＸＯＲ４８により構成され、８ビットの既約多項式の０次から７次までの項の係数（ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ）と、入力データＤｉｎ[２]と、５段目の演算回路１５の排他的論理和回路の出力データを入力して、同様の演算を行う。
【００１８】
また、７段目の演算回路１７はアンド回路ＡＮＤ４９〜ＡＮＤ５６と排他的論理和回路ＸＯＲ４９〜ＸＯＲ５６により構成され、８ビットの既約多項式の０次から７次までの項の係数（ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ）と、入力データＤｉｎ[１]と、６段目の演算回路１６の排他的論理和回路の出力データを入力して、同様の演算を行う。
【００１９】
また、８段目の演算回路１８はアンド回路ＡＮＤ５７〜ＡＮＤ６４と排他的論理和回路ＸＯＲ５７〜ＸＯＲ６４により構成され、８ビットの既約多項式の０次から７次までの項の係数（ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ）と、入力データＤｉｎ[０]と、７段目の演算回路１７の排他的論理和回路の出力データを入力して、同様の演算を行う。
【００２０】
このように、図１の単位演算回路１０では、フリップフロップＦＦ１〜ＦＦ１６は入力データＤｉｎ[０]〜Ｄｉｎ[１５]を取り込む初段のみであり、８段分の演算回路１１〜１８ではレジスタを使用しないので、１クロックで処理することが出来、高速化が可能となる。
【００２１】
本実施例では、例えば入力ビット数が１２８ビットの場合は、図２に示すように、図１に示した単位演算回路１０を１０Ａ，１０Ｂ，１０Ｃ，１０Ｄのように階層構造に接続して、４段接続とし、１２８ビット→６４ビット→３２ビット→１６ビット→８ビットの圧縮を行い、最終箇所に８個のフリップフロップで構成された出力レジスタ２０を接続する。このとき、１段目の８個の単位演算回路１０Ａで１クロック、２段目の４個の単位演算回路１０Ｂで１クロック、３段目の２個の単位演算回路１０Ｃで１クロック、４段目の１個の単位演算回路１０Ｄで１クロック、レジスタ２０で１クロックが要求されるのみである。よって、合計で５クロックで１２８ビットの入力データから８ビットのＣＲＣ符号を生成することができる。図４で説明したＣＲＣ回路が８ビットのＣＲＣ符号を生成するために１２８クロックが必要であったのと比較すると、ほぼ２５倍も高速化できる。
【００２２】
図１に示した単位演算回路１０を、そのまま、半導体集積回路内に配置し、図２のＣＲＣ演算回路を構成することも可能である。この場合には、任意の既約多項式を利用したＣＲＣ符号生成を行うことが可能である。しかし、半導体集積回路の設計時に、利用する既約多項式を決定することが可能な場合には、図１の単位演算回路１０から、不要な論理要素を省略し、簡素な回路構成で半導体集積回路内に配置することが可能である。
【００２３】
図３に、一例として、１６ビットの入力データを８ビットの既約多項式「Ｘ7＋Ｘ4＋１」で除算して８ビットのＣＲＣ符号を出力させるための単位演算回路１０’を示す。このときは、ａ＝１，ｂ＝０，ｃ＝０，ｄ＝０，ｅ＝１，ｆ＝０，ｇ＝０，ｈ＝１となるので、アンド回路は６４個が全て省略され、排他的論理和回路も４０個が省略された簡素な回路構成となる。
【符号の説明】
【００２４】
１０，１０’，１０Ａ〜１０Ｄ：単位演算回路
ＦＦ１〜ＦＦ１６，ＦＦ７１〜ＦＦ７８：フリップフロップ
ＡＮＤ１〜ＡＮＤ６４：アンド回路
ＸＯＲ１〜ＸＯＲ６４，ＸＯＲ７１〜ＸＯＲ７３：排他的論理和回路
【図１】
2014165892.tif 000003
【図２】
2014165892.tif 000004
【図３】
2014165892.tif 000005
【図４】
2014165892.tif 000006