TOP > 国内特許検索 > 符号生成装置、符号生成方法、通信装置、解析装置

符号生成装置、符号生成方法、通信装置、解析装置

国内特許コード P170013991
整理番号 (S2013-1237-N0)
掲載日 2017年4月7日
出願番号 特願2015-530833
出願日 平成26年7月30日(2014.7.30)
国際出願番号 JP2014070000
国際公開番号 WO2015019907
国際出願日 平成26年7月30日(2014.7.30)
国際公開日 平成27年2月12日(2015.2.12)
優先権データ
  • 特願2013-166128 (2013.8.9) JP
発明者
  • 藤崎 礼志
出願人
  • 国立大学法人金沢大学
発明の名称 符号生成装置、符号生成方法、通信装置、解析装置
発明の概要 本願は最大周期列の符号の生成技術に関し、従来は、nが一般の奇数の場合にCR系列が存在することまでは示せなかったため、極めて非効率な方法でしか、長い系列長を有するCR系列が生成できなかったという課題を解決する。
本願では、長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する符号生成装置100において、まず、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、有向オイラーグラフGn0を生成し、次いで、CRグラフの原型、CRグラフを生成し、最後に、CR系列を生成する。このアルゴリズムによると、CRグラフ上のオイラー回路をCRグラフに一意に変換できる。ここで、CRグラフの生成においては、CRグラフの原型に含まれる少なくとも1つの中立頂点を含む複数の頂点のそれぞれを2つの頂点に分裂させることによって生成する。
従来技術、競合技術の概要


近年、電子計算機をインフラ基盤とする産業社会において、最大周期列の応用範囲は拡大しつつある。特に、遺伝子解析系、暗号系、通信系、計算機科学系、経済・ファイナンス系など、さまざまな分野に応用されている。



従来、最大周期列を生成するために、線形フィードバックシフトレジスタ(linear feedback shift register)が通常用いられていた。線形フィードバックシフトレジスタから生成される最大周期系列はM系列と呼ばれ、擬似乱数系列として最も良く知られている。また、非線形フィードバックシフトレジスタから生成される最大周期系列の典型例であるde Bruijn系列は、M系列よりも遥かに多くの最大周期系列が存在する。



非特許文献1では、長さ2nのde Bruijn系列に対するCR(complement reverse)系列を定義し、nが偶数のときにはそれが存在しないことを指摘した。さらに、n=3、5の場合にその存在例を示した。

産業上の利用分野


本発明は、符号生成技術に関する。

特許請求の範囲 【請求項1】
長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する符号生成装置であって、
複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成するオイラーグラフ生成部と、
pを取得する取得部と、
前記オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなるように、前記取得部によって取得されたpに対するCRグラフの原型を生成する第1CRグラフ生成部と、
前記第1CRグラフ生成部によって生成されたCRグラフの原型を用いて、CRグラフを生成する第2CRグラフ生成部と、
前記第2CRグラフ生成部によって生成されたCRグラフからCR系列を生成するCR系列生成部と、
を備えることを特徴とする符号生成装置。

【請求項2】
前記オイラーグラフ生成部は、入次数と出次数が共に第1所定値となる第1頂点と、入次数と出次数が共に2となる第2頂点とを含む複数の頂点を有するように、有向オイラーグラフGn0を生成し、
前記第1CRグラフ生成部は、入次数と出次数が共に第2所定値となる第3頂点と、入次数と出次数が共に2となる複数の第4頂点と、入次数と出次数が共に1となる第5頂点とを含む複数の頂点を有するように、CRグラフの原型を生成する
ことを特徴とする請求項1に記載の符号生成装置。

【請求項3】
前記第2CRグラフ生成部は、前記第1CRグラフ生成部によって生成されたCRグラフの原型に含まれる少なくとも1つの中立頂点を含む複数の頂点のそれぞれを2つの頂点に分裂させることによって、CRグラフを生成する
ことを特徴とする請求項1に記載の符号生成装置。

【請求項4】
前記CR系列生成部は、前記pが素数でない場合、前記第2CRグラフ生成部によって生成されたCRグラフから得られるオイラー回路のうち、正規括弧構造もしくは平衡括弧構造で表されるオイラー回路を選別してCR系列を生成する
ことを特徴とする請求項1に記載の符号生成装置。

【請求項5】
長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する符号生成方法であって、
複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成するステップと、
pを決定するステップと、
生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなるように、決定されたpに対するCRグラフの原型を生成するステップと、
生成されたCRグラフの原型を用いて、CRグラフを生成するステップと、
生成されたCRグラフからCR系列を生成するステップと、
を含むことを特徴とする符号生成方法。

【請求項6】
長さ2(2p+1)のde Bruijn系列に含まれるCR系列を用いて通信を実行する通信装置であって、
複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成するオイラーグラフ生成部と、
pを取得する取得部と、
前記オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなるように、前記取得部によって取得されたpに対するCRグラフの原型を生成する第1CRグラフ生成部と、
前記第1CRグラフ生成部によって生成されたCRグラフの原型を用いて、CRグラフを生成する第2CRグラフ生成部と、
前記第2CRグラフ生成部によって生成されたCRグラフからCR系列を生成するCR系列生成部と、
前記CR系列生成部によって生成されたCR系列を用いて、送信すべき信号に対して符号化処理を実施する符号化部と、
前記符号化部によって符号化された信号を送信する送信部と、
を備えることを特徴とする通信装置。

【請求項7】
長さ2(2p+1)のde Bruijn系列に含まれるCR系列を用いて塩基配列を解析する解析装置であって、
複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、それぞれの頂点における入次数と出次数が等しくなるように、有向オイラーグラフGn0を生成するオイラーグラフ生成部と、
pを取得する取得部と、
前記オイラーグラフ生成部によって生成された有向オイラーグラフGn0を変形して、それぞれの頂点における入次数と出次数が等しくなるように、前記取得部によって取得されたpに対するCRグラフの原型を生成する第1CRグラフ生成部と、
前記第1CRグラフ生成部によって生成されたCRグラフの原型を用いて、CRグラフを生成する第2CRグラフ生成部と、
前記第2CRグラフ生成部によって生成されたCRグラフからCR系列を生成するCR系列生成部と、
前記CR系列生成部によって生成されたCR系列を用いて、塩基配列を分析する分析部と、
を備えることを特徴とする解析装置。

国際特許分類(IPC)
画像

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

JP2015530833thum.jpg
出願権利状態 公開


PAGE TOP

close
close
close
close
close
close
close