図面 (/)

技術 CRC演算装置及びCRC演算方法

出願人 パナソニック株式会社
発明者 原田昭男
出願日 2004年12月27日 (15年10ヶ月経過) 出願番号 2004-376885
公開日 2006年7月13日 (14年4ヶ月経過) 公開番号 2006-185090
状態 未査定
技術分野 エラーの検出訂正 エラー時の再試行 符号誤り検出・訂正 エラーの検出、防止
主要キーワード 演算テーブル 演算対象データ 誤り検出方式 固定領域 変更値 変更部分 演算処理量 CRC演算
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2006年7月13日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (8)

課題

演算処理量を削減することが可能なCRC演算装置及びCRC演算方法を提供すること。

解決手段

メモリ12は、固定領域の値が全て0の場合について、異なる可変領域の値を有するデータのそれぞれに対して得られるCRC演算結果を記憶する。第一のCRC演算結果取得部13は、メモリ12から、入力データから変更部分抽出部11により抽出された可変領域の値と同一の値に対応付けて記憶されている演算結果を読み出して出力する。第二のCRC演算結果取得部14は、入力データにおける可変領域が0の場合に得られる第二のCRC演算結果を出力する。XOR演算部15は、第一及び第二のCRC演算結果取得部13、14からの出力に対して排他的論理和演算し、入力データのCRC演算結果として出力する。

概要

背景

データ通信ディジタルデータ処理等において、そのデータの誤り検出方式として、巡回冗長検査(Cyclic Redundancy Check、以下、CRC)が広く使用されている。この誤り検出方式は、送信側において、伝送するデータに対して所定の生成多項式を用いてCRC符号を生成して、伝送するデータの後に付加する。受信側では、伝送されてきたデータに対して同じ生成多項式を用いてCRC符号を算出し、送信側から付加されてきたものと一致すれば伝送されたデータに誤りがないと判定し、一致しなければ誤りがあると判定するものである。

上述の誤り検出方式を使用するにあたって、一般的に、あるデータのCRC演算結果を求める場合、生成多項式を用いて1ビット単位論理演算を繰り返し行う方法や、一定数ビットに対する演算結果をテーブルとして準備しておき、対象となるデータを数ビット単位に区切り順次処理していく方法などが用いられる。

演算テーブルを用いてCRCを求めるCRC演算装置の一例として、CRC符号を演算するため、予めベクトル行列との積の演算結果をCRC演算テーブルとして用意しておき、ベクトルと行列との積を計算する場合は、CRC演算テーブルを参照して計算結果を得る2元巡回符号符号化装置があった(例えば、特許文献1参照)。
特開平9−298471号公報

概要

演算処理量を削減することが可能なCRC演算装置及びCRC演算方法を提供すること。メモリ12は、固定領域の値が全て0の場合について、異なる可変領域の値を有するデータのそれぞれに対して得られるCRC演算結果を記憶する。第一のCRC演算結果取得部13は、メモリ12から、入力データから変更部分抽出部11により抽出された可変領域の値と同一の値に対応付けて記憶されている演算結果を読み出して出力する。第二のCRC演算結果取得部14は、入力データにおける可変領域が0の場合に得られる第二のCRC演算結果を出力する。XOR演算部15は、第一及び第二のCRC演算結果取得部13、14からの出力に対して排他的論理和演算し、入力データのCRC演算結果として出力する。

目的

本発明は、上記従来の事情に鑑みてなされたものであって、演算処理量を削減することが可能なCRC演算装置及びCRC演算方法を提供することを目的とする。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

取り得る値が可変な可変領域と、値が固定された固定領域とを有するデータ形式のデータを対象として、巡回冗長検査演算を行うCRC演算装置であって、前記固定領域の値が全て0の場合について、異なる可変領域の値を有するデータのそれぞれに対して得られる巡回冗長検査の演算結果を、前記可変領域の値に対応付けて記憶する記憶手段と、前記記憶手段から、巡回冗長検査の演算の対象となる演算対象データにおける可変領域の値と同一の値に対応付けて記憶されている演算結果を読み出して、第一のCRC演算結果として出力する第一のCRC演算結果出力手段と、前記演算対象データにおける可変領域が0の場合に得られる第二のCRC演算結果を出力する第二のCRC演算結果出力手段と、前記第一のCRC演算結果と前記第二のCRC演算結果とに対して排他的論理和演算し、前記演算対象データのCRC演算結果として出力する排他的論理和演算手段と、を備えるCRC演算装置。

請求項2

請求項1記載のCRC演算装置であって、前記演算対象データから、可変領域の位置及び値を抽出する変更部分抽出手段を更に備え、前記記憶手段は、前記記憶する演算結果を、可変領域の値及び位置に対応付けて記憶し、前記第一のCRC演算結果出力手段は、前記記憶手段から、前記抽出された可変領域の位置及び値と同一の可変領域の位置及び値に対応付けて記憶されている演算結果を読み出して、第一のCRC演算結果として出力し、前記第二のCRC演算結果出力手段は、可変領域が0の場合に得られる演算結果を可変領域の位置に対応付けて保持し、前記抽出された可変領域の位置と一致した位置に対応付けられた演算結果を第二のCRC演算結果として出力するCRC演算装置。

請求項3

請求項1記載のCRC演算装置であって、前記演算対象データの可変領域の値のみが入力される変更値入力手段を更に備え、前記第一のCRC演算結果出力手段は、前記記憶手段から、前記変更値入力手段に入力された値と同一の値に対応付けて記憶されている演算結果を読み出して、第一のCRC演算結果として出力し、前記第二のCRC演算結果出力手段は、前記演算対象データの可変領域を0とした場合に得られる第二のCRC演算結果をあらかじめ保存し、出力するものであるCRC演算装置。

請求項4

取り得る値が可変な可変領域と値が固定された固定領域とを有するデータ形式のデータを対象として、巡回冗長検査の演算を行うCRC演算方法であって、前記固定領域の値が全て0の場合について、異なる可変領域の値を有するデータのそれぞれに対して得られる巡回冗長検査の演算結果が、前記可変領域の値に対応付けて記憶された記憶手段から、巡回冗長検査の演算の対象となる演算対象データにおける可変領域の値と同一の値に対応付けて記憶されている演算結果を読み出して、第一のCRC演算結果として出力するステップと、前記演算対象データにおける可変領域が0の場合に得られる第二のCRC演算結果を出力するステップと、前記第一のCRC演算結果と前記第二のCRC演算結果とに対して排他的論理和演算し、前記演算対象データのCRC演算結果として出力するステップと、を有するCRC演算方法。

技術分野

0001

本発明は、取り得る値が可変な可変領域と、値が固定された固定領域とを有するデータ形式のデータを対象として、巡回冗長検査演算を行うCRC演算装置及びCRC演算方法に関する。

背景技術

0002

データ通信ディジタルデータ処理等において、そのデータの誤り検出方式として、巡回冗長検査(Cyclic Redundancy Check、以下、CRC)が広く使用されている。この誤り検出方式は、送信側において、伝送するデータに対して所定の生成多項式を用いてCRC符号を生成して、伝送するデータの後に付加する。受信側では、伝送されてきたデータに対して同じ生成多項式を用いてCRC符号を算出し、送信側から付加されてきたものと一致すれば伝送されたデータに誤りがないと判定し、一致しなければ誤りがあると判定するものである。

0003

上述の誤り検出方式を使用するにあたって、一般的に、あるデータのCRC演算結果を求める場合、生成多項式を用いて1ビット単位論理演算を繰り返し行う方法や、一定数ビットに対する演算結果をテーブルとして準備しておき、対象となるデータを数ビット単位に区切り順次処理していく方法などが用いられる。

0004

演算テーブルを用いてCRCを求めるCRC演算装置の一例として、CRC符号を演算するため、予めベクトル行列との積の演算結果をCRC演算テーブルとして用意しておき、ベクトルと行列との積を計算する場合は、CRC演算テーブルを参照して計算結果を得る2元巡回符号符号化装置があった(例えば、特許文献1参照)。
特開平9−298471号公報

発明が解決しようとする課題

0005

しかしながら、上記従来のCRC演算装置にあっては、長さや値が様々なデータに対する柔軟性を持つ一方で、例えばテストデータのように、固定長かつ決まったフォーマットを持ち、一部の領域のみが変化するようなデータに対しても、データ長に応じた演算が必要となる。すなわち、どのようなデータフォーマットに対してもそのデータ長に応じた分の演算処理時間を必要とするといった事情があった。

0006

本発明は、上記従来の事情に鑑みてなされたものであって、演算処理量を削減することが可能なCRC演算装置及びCRC演算方法を提供することを目的とする。

課題を解決するための手段

0007

本発明のCRC演算装置は、取り得る値が可変な可変領域と、値が固定された固定領域とを有するデータ形式のデータを対象として、巡回冗長検査の演算を行うCRC演算装置であって、前記固定領域の値が全て0の場合について、異なる可変領域の値を有するデータのそれぞれに対して得られる巡回冗長検査の演算結果を、前記可変領域の値に対応付けて記憶する記憶手段と、前記記憶手段から、巡回冗長検査の演算の対象となる演算対象データにおける可変領域の値と同一の値に対応付けて記憶されている演算結果を読み出して、第一のCRC演算結果として出力する第一のCRC演算結果出力手段と、前記演算対象データにおける可変領域が0の場合に得られる第二のCRC演算結果を出力する第二のCRC演算結果出力手段と、前記第一のCRC演算結果と前記第二のCRC演算結果とに対して排他的論理和演算し、前記演算対象データのCRC演算結果として出力する排他的論理和演算手段と、を備える。

0008

この構成により、演算対象となるデータに対して、CRC演算の特性を用いて、あらかじめ記憶した演算結果を用いて排他的論理和演算を行ってCRC演算結果を求めるので、演算処理量を削減することができる。

0009

また、本発明のCRC演算装置は、前記演算対象データから、可変領域の位置及び値を抽出する変更部分抽出手段を更に備え、前記記憶手段は、前記記憶する演算結果を、可変領域の値及び位置に対応付けて記憶し、前記第一のCRC演算結果出力手段は、前記記憶手段から、前記抽出された可変領域の位置及び値と同一の可変領域の位置及び値に対応付けて記憶されている演算結果を読み出して、第一のCRC演算結果として出力し、前記第二のCRC演算結果出力手段は、可変領域が0の場合に得られる演算結果を可変領域の位置に対応付けて保持し、前記抽出された可変領域の位置と一致した位置に対応付けられた演算結果を第二のCRC演算結果として出力する。

0010

この構成により、演算対象となるデータの可変領域の位置が一定ではない場合にも、演算処理量を削減したCRC演算を行うことができる。

0011

また、本発明のCRC演算装置は、前記演算対象データの可変領域の値のみが入力される変更値入力手段を更に備え、前記第一のCRC演算結果出力手段は、前記記憶手段から、前記変更値入力手段に入力された値と同一の値に対応付けて記憶されている演算結果を読み出して、第一のCRC演算結果として出力し、前記第二のCRC演算結果出力手段は、前記演算対象データの可変領域を0とした場合に得られる第二のCRC演算結果をあらかじめ保存し、出力するものである。

0012

この構成により、演算対象となるデータの可変領域の位置が一定の場合には、可変領域の値を入力するだけで、CRC演算を行うことができる。

0013

本発明のCRC演算方法は、取り得る値が可変な可変領域と値が固定された固定領域とを有するデータ形式のデータを対象として、巡回冗長検査の演算を行うCRC演算方法であって、前記固定領域の値が全て0の場合について、異なる可変領域の値を有するデータのそれぞれに対して得られる巡回冗長検査の演算結果が、前記可変領域の値に対応付けて記憶された記憶手段から、巡回冗長検査の演算の対象となる演算対象データにおける可変領域の値と同一の値に対応付けて記憶されている演算結果を読み出して、第一のCRC演算結果として出力するステップと、前記演算対象データにおける可変領域が0の場合に得られる第二のCRC演算結果を出力するステップと、前記第一のCRC演算結果と前記第二のCRC演算結果とに対して排他的論理和演算し、前記演算対象データのCRC演算結果として出力するステップと、を有する。

0014

この方法により、演算対象となるデータに対して、CRC演算の特性を用いて、あらかじめ記憶した演算結果を用いて排他的論理和演算を行ってCRC演算結果を求めるので、演算処理量を削減することができる。

発明の効果

0015

本発明によれば、演算処理量を削減することが可能なCRC演算装置及びCRC演算方法を提供することができる。

発明を実施するための最良の形態

0016

以下、本発明の実施形態について、図面を参照して説明する。まず、巡回冗長検査(以下、CRC)演算の特性について説明する。

0017

図6は、CRC演算の特性を示す説明図であり、図6(A)は領域PにおいてXの値を有するデータ、図6(B)は領域PにおいてX、それ以外の領域において0の値を有するデータ、図6(C)は領域Pにおいて0、それ以外の領域において図6(A)に示されたデータと同じ値を有するデータをそれぞれ示す。

0018

図6(A)に示されたデータのCRC演算結果をA、図6(B)に示されたデータのCRC演算結果をB、図6(C)に示されたデータのCRC演算結果をCとすると、CRC演算結果Aは、下記の式(1)で表される。
A = B XOR C ・・・(1)
ここで、「XOR」は排他的論理和を示す。

0019

図6に示された例において、このXを可変であれば、そのXに応じた図6(B)のデータのCRC演算結果と図6(C)のデータのCRC演算結果との排他的論理和を取ることで、可変な値であるXに応じた図6(A)に示されるデータのCRC演算結果を得ることができる。

0020

本実施形態のCRC演算装置は、上記の特性を用いて、取り得る値が可変な可変領域と、値が固定された固定領域とを有するデータ形式のデータを対象としてCRC演算を行う場合に、図6(B)及び図6(C)に示されるようなデータのCRC演算結果をあらかじめ演算して記憶し、記憶した演算結果を用いて排他的論理和演算を行ってCRC演算結果を求めるものである。

0021

(第1の実施形態)
図1は、本発明の第1の実施形態に係るCRC演算装置の概略構成を示すブロック図である。

0022

図1に示すように、CRC演算装置10は、変更部分抽出部11と、メモリ12と、第一のCRC演算結果取得部13と、第二のCRC演算結果取得部14と、排他的論理和演算部(以下、XOR演算部)15とを有する構成である。

0023

変更部分抽出部11は、CRC演算の対象となる、決まったフォーマットに従う入力データから値の変化する領域(以下、可変領域)の値を抽出する。この可変領域は、図6に示されるデータの例では、領域Pに対応する部分である。

0024

メモリ12は、値の変化しない領域を0として、可変領域において取り得る全ての値に対するCRC演算の結果を記憶する。図2は、メモリ12に記憶される内容を示す説明図である。メモリ12は、可変領域P以外の値が0の場合について、可変領域Pの取り得る値0〜nを有するデータ200〜20nのそれぞれに対して得られるCRC演算結果CRC0〜CRCnを、可変領域Pの値0〜nに対応付けて記憶する。

0025

第一のCRC演算結果取得部13は、変更部分抽出部11により抽出された可変領域の値と同一の値に対応付けて記憶されているCRC演算結果をメモリ12から取得し、XOR演算部15へ出力する。例えば、変更部分抽出部11により抽出された可変領域の値がnであれば、図2に示すCRC演算結果CRCnを読み出す。

0026

第二のCRC演算結果取得部14は、決まったフォーマットに従う入力データから、可変領域を0としたデータ(例えば、図6(C)に示されたデータ)のCRCをあらかじめ演算して保持しておき、入力データに対するCRC演算時に、保持してあるCRCを取得してXOR演算部15へ出力する。

0027

XOR演算部15は、第一のCRC演算結果取得部13が取得したCRC演算結果と、第二のCRC演算結果取得部14が取得したCRC演算結果と排他的論理和を演算し、入力データに対するCRC演算結果を求め、演算で得た結果を出力データとして出力する。

0028

以上のように構成されたCRC演算装置について、図3に示すフローチャートに基づいてその動作を説明する。

0029

まず、変更部分抽出部11は、入力データより、可変領域の値を抽出する(ステップS301)。

0030

次に、第一のCRC演算結果取得部13はステップS301において変更部分抽出部11が抽出した値に対応するCRC演算結果をメモリ12から取得する(ステップS302)。

0031

第二のCRC演算結果取得部14は、あらかじめ演算して保持されている、決まったフォーマットに従う入力データから、可変領域を0としたデータ(例えば、図6(C)に示されたデータ)のCRCを取得する(ステップS303)。

0032

そして、XOR演算部15は、ステップS302において取得したCRC演算結果と、ステップS303において取得した演算結果との排他的論理和を演算し、入力データに対するCRC演算結果として出力し(ステップS304)、処理を終了する。

0033

なお、上述のCRC演算装置では、入力データの可変領域の位置が変わらない場合について説明したが、入力データの可変領域の位置が複数種類であってもよい。

0034

この場合、変更部分抽出部11は、入力データから変更部分の位置及びその値を抽出する。メモリ12は、異なる可変領域の位置に対応した、固定領域を0、可変領域の値を変化させたデータのCRC演算結果を、可変領域の位置と値に対応付けて記憶する。そして、第一のCRC演算結果取得部13では、メモリ12から抽出した可変領域の位置及び値に対応付けられたCRC演算結果を取得する。第二のCRC演算結果取得部は、入力され得る可変領域の位置に対応し、それぞれ可変領域を0としたデータのCRC演算結果をあらかじめ保持し、抽出された可変領域の位置に応じてCRC演算結果をXOR演算部15に出力する。

0035

この構成により、演算対象となるデータの可変領域の位置が一定ではない場合にも、演算処理量を削減したCRC演算を行うことができる。

0036

また、入力データの可変領域が複数あり、それらが同時に可変となっていてもよい。図7は、複数の領域が同時に可変な場合のCRC演算の説明図である。

0037

図7に示すように、可変領域がP,Q,Rの3箇所である場合、メモリ12は、可変領域P以外が0で可変領域Pの取り得る値全てに対するCRCと、可変領域Q以外が0で可変領域Qの取り得る値全てに対するCRCと、可変領域R以外が0で可変領域Rの取り得る値全てに対するCRCと、を記憶する。

0038

また、第二のCRC演算結果取得部14は、可変領域P,Q,Rに対応する部分が0の場合のCRCをあらかじめ演算し、保持しておく。この演算結果をEとする(図7(E)参照)。

0039

そして、図7(A)に示すように、CRCの演算対象となるデータが、可変領域Pの値がx、可変領域Qの値がy、可変領域Rの値がzである場合、第一のCRC演算結果取得部13は、メモリ12から、可変領域P以外が0で可変領域Pの値がxの場合のCRC演算結果であるX(図7(B)参照)と、可変領域Q以外が0で可変領域Qの値がyの場合のCRC演算結果であるY(図7(C)参照)と、可変領域R以外が0で可変領域Rの値がzの場合のCRC演算結果であるZ(図7(D)参照)と、を読み出して取得する。

0040

また、第二のCRC演算結果取得部14は、あらかじめ保持されているCRC演算結果であるEを取得する。

0041

このとき、図7(A)に示されるCRC演算対象となるデータのCRCをαとすると、下記の式(2)で表される。
α = X XOR Y XOR Z XOR E ・・・ (2)

0042

この構成により、複数の領域が同時に可変となっている場合にも、演算処理量を削減したCRC演算を行うことができる。

0043

このような本発明の第1の実施形態によれば、演算対象となる入力データから可変領域を抽出し、CRC演算の特性を用いて、あらかじめ記憶した演算結果を用いて排他的論理和演算を行ってCRC演算結果を求めるので、演算処理量を削減することができる。

0044

(第2の実施形態)
図4は、本発明の第2の実施形態に係るCRC演算装置の概略構成を示すブロック図である。同図において、第1の実施形態で説明した図1重複する部分には同一の符号を付す。

0045

本実施形態のCRC演算装置40は、可変領域の位置が不変で、かつ固定領域の取り得る値の配列の種類が一種類のみである場合に用いられるものである。図2に示すように、本実施形態のCRC演算装置40は、可変領域の値が0、固定領域の値が前述の配列であるデータのCRC演算結果を記憶する第二のCRC演算結果記憶部41が設けられており、そのCRC演算結果をXOR演算部15に出力する。

0046

また、第一のCRC演算結果取得部13には、可変領域の値が入力され、メモリ12から可変領域の値に対応付けられた、固定領域0のデータのCRC演算結果を読み出してXOR演算部15に出力する。

0047

以上のように構成されたCRC演算装置40について、図5を用いてその動作を説明する。

0048

まず、第一のCRC演算結果取得部13が入力された可変領域の値を取得し(ステップS501)、その取得した可変領域の値に対応するCRC演算結果をメモリ12から取得する(ステップS502)。

0049

XOR演算部15が、第二のCRC演算結果記憶部41に記憶されているCRC演算結果を取得し(ステップS503)、その取得したCRC演算結果と、ステップS502で取得した値が可変領域の値に対応するCRC演算結果とで排他的論理和を演算し、入力された可変領域の値に対応したデータのCRC演算結果として、出力する(ステップS504)。

0050

このような本発明の第2の実施形態によれば、演算対象となるデータの可変領域の位置が一定の場合には、可変領域の値を入力するだけで、CRC演算を行うことができる。

0051

本発明のCRC演算装置及びCRC演算方法は、演算処理量を削減することが可能な効果を有し、一部領域のみが可変なテストデータを生成する装置におけるCRC演算部等に有用である。

図面の簡単な説明

0052

本発明の第1の実施形態に係るCRC演算装置の概略構成を示すブロック図
メモリに記憶される内容を示す説明図
第1の実施形態に係るCRC演算装置の動作を示すフローチャート図
本発明の第2の実施形態に係るCRC演算装置の概略構成を示すブロック図
第2の実施形態に係るCRC演算装置の動作を示すフローチャート図
CRC演算の特性を示す説明図
複数の領域が同時に可変な場合のCRC演算の説明図

符号の説明

0053

10、40CRC演算装置
11変更部分抽出部
12メモリ
13 第一のCRC演算結果取得部
14 第二のCRC演算結果取得部
15 XOR演算部
41 第二のCRC演算結果記憶部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ