TOP > 国内特許検索 > 演算回路設定方法

演算回路設定方法 コモンズ 新技術説明会

国内特許コード P120007936
整理番号 FU505
掲載日 2012年9月26日
出願番号 特願2012-206395
公開番号 特開2014-064065
登録番号 特許第5999634号
出願日 平成24年9月19日(2012.9.19)
公開日 平成26年4月10日(2014.4.10)
登録日 平成28年9月9日(2016.9.9)
発明者
  • 岩田 賢一
  • 福間 慎治
  • 大島 怜也
出願人
  • 国立大学法人福井大学
発明の名称 演算回路設定方法 コモンズ 新技術説明会
発明の概要 【課題】本発明は、並列処理を行う上で必要となる最小限のXOR演算回数により演算処理を行うことができる符号化・復号化装置を提供することを目的とする。
【解決手段】符号化・復号化処理部10は、所定の規則性を有する検査行列に基づいて入力データに対応するハミング符号の符号語を生成する符号化処理を行うとともに検査行列に基づいてハミング符号の受信語のエラー位置を検出する復号化処理を行い、ハミング符号が符号長2m-1及び情報ビット数2m-m-1の2元ハミング符号である場合に、XOR演算回数を(2m+1-2m-2)回処理して復号化処理する演算回路を備えている。
【選択図】図1
従来技術、競合技術の概要



記憶処理装置や通信処理装置等のデータ処理装置は、一般的にデータの誤り検出及び訂正を行う誤り訂正機能を備えている。誤り訂正機能としては、1ビット訂正可能なハミング符号(短縮化ハミング符号語)を用いた符号化・復号化方式が提案されている。こうした符号化・復号化方式では、情報ビット列(情報ベクトル)及び生成行列に基づいてハミング符号を生成する符号化処理を実行するとともに、生成行列に対応する検査行列(パリティ検査行列)及びハミング符号に基づいてエラー位置を検出する復号化処理を実行する。





情報ビット列は、記憶処理装置では記録媒体に記憶される入力データが該当し、通信処理装置では送信データが該当する。そして、ハミング符号は、情報ビット列及びパリティビット列(パリティデータ)を組み合せて構成される。復号化処理では、記憶処理装置では記録媒体から読み出されるハミング符号からなる出力データのエラー位置を検出し、通信処理装置では受信データのエラー位置を検出して、そのエラー位置を示すデータ(以下「シンドローム(syndrome)」と称する)を生成する。エラー訂正処理では、復号化処理により検出されたエラー位置のエラービットを訂正してデータ出力処理を行う。





簡単な誤り訂正符号の1つである2元ハミング符号を用いた符号化・復号化装置における排他的論理和(XOR)の演算処理について考える。2元体をF2と表記し、その元を0と1で表す。2元体での加法については、以下の通り表記する。

【数1】




なお、この表記において、2項間の記号は排他的論理和(XOR)である。

2以上の任意の整数mに対して、F2={0,1}上のすべての非零のm次元ベクトルを列として並べたm行2m-1列の行列を検査行列として定義される符号は符号長2m-1、情報ビット数2m-m-1の2元ハミング符号であり、(2m-1,2m-m-1)ハミング符号と表記する。(2m-1,2m-m-1)ハミング符号を定める検査行列をHと表記する。特に、検査行列のj列目hjT

jT=(h1,j,h2,j,…,hi,j,…,hm,j)∈F2m

とし、

【数2】




を満たすようにhjを定めた検査行列をHmと表記する。ただし、hTはhの転置を表す。(2m-1,2m-m-1)ハミング符号は最小距離が3であり、ハミング限界を等号で満たす完全符号である(非特許文献1参照)。





そして、(2m-1,2m-m-1)ハミング符号における検査行列Hでの列の並べ方は任意であり、巡回符号である(2m-1,2m-m-1)ハミング符号はシフトレジスタを用いたm段符号器や2m-m-1段符号器及び巡回ハミング符号の復号器を用いた符号化・復号化装置によって実現することができる(非特許文献1参照)。





これに対して、符号器及び復号器の高速化を図る方法として、符号語や復号結果の各ビットを並列に出力する並列符号器及び並列復号器が提案されている(特許文献1参照)。

産業上の利用分野



本発明は、記憶処理装置、通信処理装置等のデータ処理装置に用いられる符号化・復号化装置及び符号化・復号化処理を行う演算回路の設定方法に関する。

特許請求の範囲 【請求項1】
符号長2m-1及び情報ビット数2m-m-1の2元ハミング符号の受信語rj,j=1,2,…,2m-1に対してXOR演算を複数回行ってエラー位置を検出するシンドロームsi,i=1,2,…,mを生成する復号化処理の演算回路設定方法であって、以下の規則1から規則4に基づいて表記された順序でXOR演算を行うように演算回路を構成する演算回路設定方法。
<規則1>
左端の列に上から順にs1からsmを並べる。
<規則2>
jの二進表記であるbm-1m-2…b0,bi ∈{0,1}について以下の値を求め、
【数14】


この値が同じものを小さい値1から大きい値mの順に左から右に列として配置し、各列ではjの小さい値から大きい値の順に上から下に配置する。
<規則3>
規則2で作成した配置図において、bm-1m-2…b0を値0か値1の1ビットを保持する節点jとし、各節点jの保持する値をv(j)として、演算開始時刻での値v(j)をrjとする。左端の列に配置された節点j=2i-1をsiに対応させ、siを求めるrjのXOR演算の演算式に基づいてrjに対応する節点j同士を線で結ぶ。
<規則4>
j<j’を満たす節点jと節点j’との間を結ぶ線がある場合には、演算開始時刻から1回のXOR演算に起因する遅延時間に基づいて設定されたタイミングでv(j)及びv(j’)のXOR演算を行い、節点jの値をXOR演算結果とする。

【請求項2】
m=k-1(kは、3以上の自然数)におけるシンドロームを生成する演算回路に基づいてm=kにおけるシンドロームを生成する演算回路を設定する請求項1に記載された演算回路設定方法。
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2012206395thum.jpg
出願権利状態 登録
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記までご連絡ください。


PAGE TOP

close
close
close
close
close
close
close