Top > Search of Japanese Patents > (In Japanese)符号生成装置、符号生成方法、通信装置、解析装置

(In Japanese)符号生成装置、符号生成方法、通信装置、解析装置

Patent code P170013991
File No. (S2013-1237-N0)
Posted date Apr 7, 2017
Application number P2015-530833
Patent number P6261014
Date of filing Jul 30, 2014
Date of registration Dec 22, 2017
International application number JP2014070000
International publication number WO2015019907
Date of international filing Jul 30, 2014
Date of international publication Feb 12, 2015
Priority data
  • P2013-166128 (Aug 9, 2013) JP
Inventor
  • (In Japanese)藤崎 礼志
Applicant
  • (In Japanese)国立大学法人金沢大学
Title (In Japanese)符号生成装置、符号生成方法、通信装置、解析装置
Abstract (In Japanese)本願は最大周期列の符号の生成技術に関し、従来は、nが一般の奇数の場合にCR系列が存在することまでは示せなかったため、極めて非効率な方法でしか、長い系列長を有するCR系列が生成できなかったという課題を解決する。
本願では、長さ2(2p+1)のde Bruijn系列に含まれるCR系列を生成する符号生成装置100において、まず、複数の頂点のそれぞれが辺で結ばれたde BruijnグラフGnを用いて、有向オイラーグラフGn0を生成し、次いで、CRグラフの原型、CRグラフを生成し、最後に、CR系列を生成する。このアルゴリズムによると、CRグラフ上のオイラー回路をCRグラフに一意に変換できる。ここで、CRグラフの生成においては、CRグラフの原型に含まれる少なくとも1つの中立頂点を含む複数の頂点のそれぞれを2つの頂点に分裂させることによって生成する。
Outline of related art and contending technology (In Japanese)

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

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

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

Field of industrial application (In Japanese)

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

Scope of claims (In Japanese)
【請求項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(International Patent Classification)
Drawing

※Click image to enlarge.

JP2015530833thum.jpg
State of application right Registered


PAGE TOP

close
close
close
close
close
close
close