Top > Search of International Patents > CODE GENERATING DEVICE, CODE GENERATING METHOD, COMMUNICATION DEVICE, AND ANALYSIS DEVICE

CODE GENERATING DEVICE, CODE GENERATING METHOD, COMMUNICATION DEVICE, AND ANALYSIS DEVICE meetings

Foreign code F150008330
Posted date Apr 22, 2015
Country WIPO
International application number 2014JP070000
International publication number WO 2015019907
Date of international filing Jul 30, 2014
Date of international publication Feb 12, 2015
Priority data
  • P2013-166128 (Aug 9, 2013) JP
Title CODE GENERATING DEVICE, CODE GENERATING METHOD, COMMUNICATION DEVICE, AND ANALYSIS DEVICE meetings
Abstract The present application solves the problem that with regards to technology for generating a code of a maximum-length linearly recurring sequence, conventionally, it was not indicated that a complement reverse (CR) sequence is present when n is an ordinary odd number, and so only by means of an extremely inefficient method was it possible to generate a CR sequence having a long sequence length. In the present application, a code generating device (100) that generates a CR sequence contained in a de Bruijn sequence having a length of 2(2p+1) is such that first, a directed Eulerian graph (Gn0) is generated using a de Bruijn graph (Gn) in which a plurality of vertices are respectively joined by edges, and then a CR graph archetype and CR graph are generated, and finally a CR sequence is generated. By means of this algorithm, it is possible to uniquely convert an Eulerian circuit on a CR graph to a CR graph. Here, when generating CR graph, each of a plurality of vertices including at least one neutral vertex contained in the CR graph archetype are split into two vertices to perform the generation.
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系列を用いて、塩基配列を分析する分析部と、
を備えることを特徴とする解析装置。
  • Applicant
  • ※All designated countries except for US in the data before July 2012
  • KANAZAWA UNIVERSITY
  • Inventor
  • FUJISAKI HIROSHI
IPC(International Patent Classification)
Specified countries National States: AE AG AL AM AO AT AU AZ BA BB BG BH BN BR BW BY BZ CA CH CL CN CO CR CU CZ DE DK DM DO DZ EC EE EG ES FI GB GD GE GH GM GT HN HR HU ID IL IN IR IS JP KE KG KN KP KR KZ LA LC LK LR LS LT LU LY MA MD ME MG MK MN MW MX MY MZ NA NG NI NO NZ OM PA PE PG PH PL PT QA RO RS RU RW SA SC SD SE SG SK SL SM ST SV SY TH TJ TM TN TR TT TZ UA UG US UZ VC VN ZA ZM ZW
ARIPO: BW GH GM KE LR LS MW MZ NA RW SD SL SZ TZ UG ZM ZW
EAPO: AM AZ BY KG KZ RU TJ TM
EPO: AL AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LT LU LV MC MK MT NL NO PL PT RO RS SE SI SK SM TR
OAPI: BF BJ CF CG CI CM GA GN GQ GW KM ML MR NE SN TD TG

PAGE TOP

close
close
close
close
close
close