(57)【特許請求の範囲】
【請求項１】
符号化処理の対象となる数列を示す符号化対象シンボル列と、復号化処理装置と自装置とで共通に用いられて、当該符号化対象シンボル列と同一の進数及び桁数による数列を示すパイロットシンボル列と、の桁毎に演算を実行して、演算後シンボル列を生成した後、さらに、生成された前記演算後シンボル列と、前記パイロットシンボル列とを桁毎に前記演算を実行することを少なくとも一回以上繰り返して、少なくとも一つ以上の前記演算後シンボル列を生成するシンボル列演算手段と、
前記符号化対象シンボル列と、前記演算後シンボル列とを、結合して結合シンボル列を生成するシンボル列結合手段と、
前記結合シンボル列を出力処理する出力処理手段と、
を備えたことを特徴とする符号化処理装置。
【請求項２】
前記シンボル列演算手段は、所定の進数から１減じた回数まで繰り返すこと、
を特徴とする請求項１に記載の符号化処理装置。
【請求項３】
所定の桁数に所定の数値が設定された前記符号化対象シンボル列を入力処理する入力処理手段を、さらに備えることを特徴とする請求項１又は２に記載の符号化処理装置。
【請求項４】
線形誤り訂正符号で符号化された符号化対象シンボル列を入力処理する入力処理手段を、さらに備え、
前記シンボル列演算手段は、入力処理された前記符号化対象シンボル列と、前記線形誤り訂正符号の符号語である前記パイロットシンボル列と、を桁毎に加算を実行して、演算後シンボル列を生成すること、
を特徴とする請求項１乃至３のいずれか一つに記載の符号化処理装置。
【請求項５】
前記線形誤り訂正符号が、短縮化符号であることを特徴とする請求項４に記載の符号化処理装置。
【請求項６】
シンボル列演算手段が、符号化処理の対象となる数列を示す符号化対象シンボル列と、復号化処理方法と共通に用いられて、当該符号化対象シンボル列と同一の進数及び桁数による数列を示すパイロットシンボル列と、の桁毎に演算を実行して、演算後シンボル列を生成した後、さらに、生成された前記演算後シンボル列と、前記パイロットシンボル列とを桁毎に前記演算を実行することを少なくとも一回以上繰り返して、少なくとも一つ以上の前記演算後シンボル列を生成するシンボル列演算ステップと、
シンボル列結合手段が、前記符号化対象シンボル列と、前記演算後シンボル列とを、結合して結合シンボル列を生成するシンボル列結合ステップと、
出力処理手段が、前記結合シンボル列を出力処理する出力処理ステップと、
を有することを特徴とする符号化処理方法。
【請求項７】
前記シンボル列演算ステップは、所定の進数から１減じた回数まで繰り返すこと、
を特徴とする請求項６に記載の符号化処理方法。
【請求項８】
入力処理手段が、所定の桁数に所定の数値が設定された前記符号化対象シンボル列を入力処理する入力処理ステップを、さらに有することを特徴とする請求項６乃至７のいずれか一つに記載の符号化処理方法。
【請求項９】
請求項６乃至８のいずれか１つに記載の符号化処理方法をコンピュータに実行させる符号化処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、シンボル列の符号化処理を行う符号化処理装置、符号化処理方法、及び符号化処理プログラムに関するものである。
【背景技術】
【０００２】
近年、ネットワーク技術及びコンピュータ技術の発達に伴い、様々な情報が利用者に対して提供される傾向にある。情報の提供には、ネットワークインフラを用いる場合もあるし、電子データを紙媒体などに印刷して提供される場合もある。
【０００３】
例えば、著作権保護、トレース、偽造防止、改ざん検知、メタ情報の付加などの目的で、画像、動画、音声などのコンテンツに任意の情報を埋め込む電子透かし技術の検討が進められている。電子透かしは、様々な処理が加えられたコンテンツから、埋め込まれた情報シンボルを正しく抽出できることが要求される。しかしながら、電子透かしが埋め込まれた紙媒体の劣化や、読み取り誤りなどが生じることで、情報を正しく抽出できない場合もある。このような問題を解決するために、情報の埋め込み方法や符号化方法の工夫から解決が試みられている。
【０００４】
例えば、特許文献１では、一つの情報シンボルを分散させて埋め込む方式が提案されている。さらには、特許文献２では、誤り訂正符号により埋込情報を符号化する方式が提案されている。
【０００５】
【特許文献１】特開２００３−１２５１８９号公報
【特許文献２】特開２０００−１８７４４１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、抽出する情報においては、当該情報を埋め込むために使用されるシンボルの違いに応じて誤りに偏りが生じる場合が多い。この場合、特許文献１及び特許文献２において抽出精度が低下するという問題がある。
【０００７】
本発明は、上記に鑑みてなされたものであって、情報を埋め込むために使用されるシンボルの違いに応じて誤りが偏る場合でも適切に情報を抽出可能とする符号化処理装置、符号化処理方法、及び符号化処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するために、請求項１にかかる発明は、符号化処理の対象となる数列を示す符号化対象シンボル列と、復号化処理装置と自装置とで共通に用いられて、当該符号化対象シンボル列と同一の進数及び桁数による数列を示すパイロットシンボル列と、の桁毎に演算を実行して、演算後シンボル列を生成した後、さらに、生成された前記演算後シンボル列と、前記パイロットシンボル列とを桁毎に前記演算を実行することを少なくとも一回以上繰り返して、少なくとも一つ以上の前記演算後シンボル列を生成するシンボル列演算手段と、前記符号化対象シンボル列と、前記演算後シンボル列とを、結合して結合シンボル列を生成するシンボル列結合手段と、前記結合シンボル列を出力処理する出力処理手段と、を備えたことを特徴とする。
【００１０】
また、請求項２にかかる発明は、請求項１にかかる発明において、前記シンボル列演算手段は、所定の進数から１減じた回数まで繰り返すこと、を特徴とする。
【００１１】
また、請求項３にかかる発明は、請求項１又は２にかかる発明において、所定の桁数に所定の数値が設定された前記符号化対象シンボル列を入力処理する入力処理手段を、さらに備えることを特徴とする。
【００１２】
また、請求項４にかかる発明は、請求項１乃至３のいずれか一つにかかる発明において、線形誤り訂正符号で符号化された符号化対象シンボル列を入力処理する入力処理手段を、さらに備え、前記シンボル列演算手段は、入力処理された前記符号化対象シンボル列と、前記線形誤り訂正符号の符号語である前記パイロットシンボル列と、を桁毎に加算を実行して、演算後シンボル列を生成すること、を特徴とする。
【００１３】
また、請求項５にかかる発明は、請求項４にかかる発明において、前記線形誤り訂正符号が、短縮化符号であることを特徴とする。
【００２０】
また、請求項６にかかる発明は、シンボル列演算手段が、符号化処理の対象となる数列を示す符号化対象シンボル列と、復号化処理方法と共通に用いられて、当該符号化対象シンボル列と同一の進数及び桁数による数列を示すパイロットシンボル列と、の桁毎に演算を実行して、演算後シンボル列を生成した後、さらに、生成された前記演算後シンボル列と、前記パイロットシンボル列とを桁毎に前記演算を実行することを少なくとも一回以上繰り返して、少なくとも一つ以上の前記演算後シンボル列を生成するシンボル列演算ステップと、シンボル列結合手段が、前記符号化対象シンボル列と、前記演算後シンボル列とを、結合して結合シンボル列を生成するシンボル列結合ステップと、出力処理手段が、前記結合シンボル列を出力処理する出力処理ステップと、を有することを特徴とする。
【００２２】
また、請求項７にかかる発明は、請求項６にかかる発明において、前記シンボル列演算ステップは、所定の進数から１減じた回数まで繰り返すこと、を特徴とする。
【００２３】
また、請求項８にかかる発明は、請求項６乃至７のいずれか一つにかかる発明において、入力処理手段が、所定の桁数に所定の数値が設定された前記符号化対象シンボル列を入力処理する入力処理ステップを、さらに有することを特徴とする。
【００２６】
また、請求項９にかかる発明は、請求項６乃至８のいずれか１つに記載の符号化処理方法をコンピュータに実行させる符号化処理プログラムであることを特徴とする。
【発明の効果】
【００２８】
本願発明によれば、パイロットシンボル列の加算により異なる元が含まれることになるので、出力された結合シンボル列が伝達しているときに誤りが生じた場合でも符号化対象シンボル列を復号する精度を向上させることが可能という効果を奏する。
【発明を実施するための最良の形態】
【００２９】
以下に添付図面を参照して、この発明にかかる符号化処理装置、符号化処理方法、符号化処理プログラムの最良な実施の形態を詳細に説明する。
【００３０】
（第１の実施の形態）
図１は、第１の実施の形態にかかる符号化処理装置１００と復号化処理装置１５０の構成を示すブロック図である。図１に示すように、符号化処理装置１００で符号化された符号化シンボル列が通信路を介して、復号化処理装置１５０に入力される。その後、復号化処理装置１５０が入力された符号化シンボル列に対して復号化処理を施す。なお、通信路とは、ネットワーク経由に制限するものではなく、例えば紙媒体で受け渡しなどを含み、符号化された情報になんらかの変化を及ぼすあらゆる伝達手法による伝達が含まれるものとする。
【００３１】
図１に示すように符号化処理装置１００の内部は、入力処理部１０１と、シンボル列加算部１０２と、シンボル列結合部１０３と、符号化シンボル列出力部１０４と、を備え、入力処理されたシンボル列に対して、符号化処理を施す。また、復号化処理装置１５０は、復号対象シンボル列入力処理部１５１と、シンボル列分割部１５２と、シンボル列減算部１５３と、数値決定部１５４と、数値結合部１５５と、誤り訂正符号復号部１５６と、出力部１５７とを備え、入力されたシンボル列Ｓ１に対して復号化処理を施す。まず、符号化処理装置１００の各構成について説明する。
【００３２】
入力処理部１０１は、復号化処理を施すシンボル列の入力処理を行う。シンボルの元の数は５とし、シンボルの元の四則演算は５を法とする演算で行うことにする。これにより、位数５のガロア体（有限体）＝ＧＦ(５)を構成することができる。具体的には、本実施の形態で入力処理の対象となるシンボル列Ｓ１は、４桁５進数による数列とする。この４桁のうち２桁はパリティとして利用しても良い。
【００３３】
以下の説明において、符号化対象のシンボル列Ｓ１は(３，１，０，２)とする。符号化対象シンボル列はＧＦ（５）上のリードソロモン符号（生成多項式は(x-2)*(x-4)）で符号化されている。
【００３４】
シンボル列加算部１０２は、符号化対象として入力処理されたシンボル列Ｓ１と、パイロットシンボル列と、の桁毎に加算処理を１回から４回だけ繰り返し、４個の演算後シンボル列を生成する。なお、本実施の形態では四測演算のうち加算を使用するが、乗算など他の演算を用いても良い。
【００３５】
パイロットシンボル列とは、符号化処理装置１００の符号化処理及び復号化処理装置１５０の復号化処理で利用されるシンボル列とする。当該パイロットシンボル列は、‘０’以外の数値からなる４桁５進数の数列とする。また、パイロットシンボル列は上記リードソロモン符号の符号語となっており、５回繰り返して加算すると零ベクトルとなる。
【００３６】
また、パイロットシンボル列は、ｑを素数としてＧＦ（ｑ）上であれば、０以外の元を用いて構成すれば十分である。しかしながら、ｑが素数でない場合は、このようにパイロットシンボル列を構成することができない。しかしながら、例えば計算機分野で重要なＧＦであるＧＦ（２の自然数乗）を用いる場合、元を０／１に分解して通信するという前提のもと、パイロットシンボル列を(１１…１，１１…１，…，１１…１)と全ての桁が１になるように設定すれば、０／１を均等に出現させることができる。
【００３７】
本実施の形態にかかる符号化処理装置１００において、入力処理されたシンボル列Ｓ１に対して、パイロットシンボル列を１回〜‘４’回まで繰り返し加算する。これは、元の数‘５’から‘１’減じた数が‘４’であることに基づく。これは元の数が素数の場合に限り、素数以外では異なることになる。
【００３８】
入力処理されたシンボル列が“３１０２”で、パイロットシンボル列が“３４２１”の場合について説明する。シンボル列加算部１０２は、パイロットシンボル列の一回加算で演算後シンボル列“１０２３”を生成し、二回加算で演算後シンボル列“４４４４”を生成し、三回加算で演算後シンボル列“２３１０”を生成し、四回加算で演算後シンボル列“０２３１”を生成する。
【００３９】
入力処理されたシンボル列及び演算後シンボル列のそれぞれの桁の数値を確認すると、０〜４の全ての数値（元）が出現しているのが確認できる。例えば左の一桁目では、入力処理のシンボル列で‘３’であり、一回加算後の演算後シンボル列で‘１’であり、二回加算後の演算後シンボル列で‘４’であり、三回加算後の演算後シンボル列で‘２’であり、四回加算後の演算後シンボル列で‘０’である。
【００４０】
シンボル列結合部１０３は、入力処理されたシンボル列及び四個の演算後シンボル列を結合する。具体的には、入力処理されたシンボル列、一回加算後の演算後シンボル列、二回加算後の演算後シンボル列、三回加算後の演算後シンボル列及び四回加算後の演算後シンボル列の順に結合する。以下、結合したシンボル列を結合シンボル列と呼ぶ。
【００４１】
上述した例では、結合シンボル列は、“３１０２１０２３４４４４２３１００２３１”となる。当該結合シンボル列では、全ての元（数値０〜４）が等しく出現していることが確認できる。
【００４２】
符号化シンボル列出力部１０４は、結合シンボル列を、符号化処理を施した後のシンボル列Ｓ２として出力する。
【００４３】
本実施の形態にかかる符号化処理装置１００では、上述した処理により作成された符号化シンボル列を出力している。ところで、従来から、画像データに埋込等を行う場合、耐性を強くするためにシンボル列を繰り返して埋め込んでいた。これに対し、本実施の形態にかかる符号化処理装置１００では、同一シンボル列を元の異ならせた上で繰り返し埋め込むことで、単に繰り返しシンボル列を埋め込むより、耐性を強くすることができる。
【００４４】
そして、出力されたシンボル列Ｓ２は、通信路上で伝達されているうちに誤りが発生している。そして、当該誤りを含む復号対象シンボル列Ｓ３が、復号化処理装置１５０に入力処理される。次に、復号化処理装置１５０の各構成について説明する。
【００４５】
復号対象シンボル列入力処理部１５１は、復号対象シンボル列Ｓ３の入力処理を行う。復号対象シンボル列Ｓ３は、通信路上で誤りが生じた５進数２０桁の数列とする。なお、復号対象シンボル列Ｓ３に含まれるシンボルにおいては、誤りに偏りが生じているものとする。
【００４６】
例えば、シンボル列毎に異なる電圧値として伝達させた場合、所定のシンボルに限り異なるシンボルと誤って認識される等が考えられる。又はシンボル列が紙媒体に印刷されていた場合、読み取り時に所定のシンボルに限り、他のシンボルと誤って認識される等が考えられる。このような誤りに偏りが生じている場合、従来の手法では正確に抽出できる確率が低下していた。これに対し、本実施の形態にかかる符号化処理及び復号化処理においては、シンボル毎に変化する確率が異なる場合、具体的にはシンボル毎に当該シンボルが自身のシンボル以外に変化する確率が異なる場合に有効である。
【００４７】
シンボル列分割部１５２は、入力処理された復号対象シンボル列Ｓ３を、４桁ごとに分割し、複数のシンボル列を生成する。入力処理された復号対象シンボル列Ｓ３なので、分割後に５個のシンボル列が生成される。
【００４８】
シンボル列減算部１５３は、分割されたシンボル列と、パイロットシンボル列と、の桁毎に、減算を行う。この際、分割されたシンボル列の順序に従って、減算を繰り返す回数を異ならせる。例えば、分割された１個目のシンボル列には減算を行わず、分割された２個目のシンボル列には１回減算を行う。さらに、３個目のシンボル列には２回減算を行い、４個目のシンボル列には３回減算を行い、５個目のシンボル列には４回減算を行う。このように、分割された順番が１増加すると、減算される回数も１増加する。
【００４９】
数値決定部１５４は、シンボル列減算部１５３により減算処理が行われたシンボル列において、当該複数のシンボル列の桁毎に最も頻度が高い数値を当該桁の数値として決定する。
【００５０】
数値結合部１５５は、数値決定部１５４により決定された桁毎の数値を結合して、準復号シンボル列を生成する。
【００５１】
誤り訂正符号復号部１５６は、準復号シンボル列に対して復号処理を行い、復号シンボル列を取得する。出力部１５７は、復号シンボル列を出力する。
【００５２】
次に、以上のように構成された本実施の形態にかかる符号化処理装置１００におけるシンボル列に対して符号化処理を施すまでの処理手順について説明する。図２は、本実施の形態にかかる符号化処理装置１００における上述した処理の手順を示すフローチャートである。
【００５３】
まず、入力処理部１０１が、符号化対象となるシンボル列Ｓ１の入力処理を行う（ステップＳ２０１）。
【００５４】
次に、シンボル列加算部１０２が、入力処理したシンボル列Ｓ１を加算対象に設定する（ステップＳ２０２）。このシンボル列Ｓ１を、（３，１，０，２）とする。
【００５５】
そして、シンボル列加算部１０２が、加算対象のシンボル列に対して、パイロットシンボル列を加算して、新たなシンボル列を生成する（ステップＳ２０３）。パイロットシンボル列は、(３，４，２，１)とする。加算処理が１回目であれば、演算後シンボル列として（１，０，２，３）を生成する。
【００５６】
次に、シンボル列加算部１０２は、加算処理が元の数―１か否か判断する（ステップＳ２０４）。なお、本実施の形態では元の数が５なので、加算処理が４回か否か判断する。
【００５７】
そして、加算処理を行った回数が４回より小さい場合（ステップＳ４０４：Ｎｏ）、ステップＳ２０３で生成された演算後シンボル列が、新たな加算対象のシンボル列と設定される（ステップＳ２０５）。
【００５８】
このように、処理が繰り返されることで、入力処理したシンボル列にパイロットシンボル列を１〜４回繰り返し加算した、演算後シンボル列（１，０，２，３）、（４，４，４，４）、（２，３，１，０）、（０，２，３，１）が生成される。
【００５９】
そして、シンボル列加算部１０２が、加算処理を行った回数が４回以上となった場合（ステップＳ４０４：Ｙｅｓ）、シンボル列結合部１０３が、入力処理したシンボル列と、生成した演算後シンボル列とを結合する（ステップＳ４０６）。結合したシンボル列は、（３，１，０，２，１，０，２，３，４，４，４，４，２，３，１，０，０，２，３，１）
【００６０】
そして、符号化シンボル列出力部１０４が、結合したシンボル列を、符号化シンボル列として出力する（ステップＳ４０７）。
【００６１】
図３は、符号化処理装置１００により出力される符号化シンボル列の概念を示した図である。図３に示すように、符号化対象となるシンボル列にパイロットシンボル列を繰り返し加算して４個の演算後シンボル列を取得する。そして、符号化シンボル列と、４個の演算後シンボル列との、末尾と先頭とを結合して符号化シンボル列（３，１，０，２，１，０，２，３，４，４，４，４，２，３，１，０，０，２，３，１）を生成する。
【００６２】
次に、以上のように構成された本実施の形態にかかる復号化処理装置１５０におけるシンボル列に対して復号化処理を施すまでの処理について説明する。図４は、本実施の形態にかかる復号化処理装置１５０における上述した処理の手順を示すフローチャートである。
【００６３】
ところで、復号対象となるシンボル列は、１と２が０に誤る通信路を通り、(３，０，０，０、０，０，０，３，４，４，４，４，０，３，０，０，０，０，３，０)に変化したものとする。
【００６４】
まず、復号対象シンボル列入力処理部１５１が、復号対象シンボル列の入力処理を行う（ステップＳ４０１）。
【００６５】
次に、シンボル列分割部１５２が、復号対象シンボル列を、所定の桁毎に分割する（ステップＳ４０２）。本実施の形態においては、４桁（４シンボル）毎に分割を行うものとする。これにより、５個のシンボル列（３，０，０，０）、（０，０，０，３）、（４，４，４，４）、（０，３，０，０）、（０，０，０，３）が生成される。これらシンボル列を右から順に１番目、２番目と便宜上番号を割り当てる。
【００６６】
そして、シンボル列減算部１５３が、変数Ｎに‘０’を設定する（ステップＳ４０３）。次に、シンボル列減算部１５３が、Ｎ＋１番目のシンボル列に対して、パイロットシンボル列をＮ回減算する処理を行う（ステップＳ４０４）。例えば、最初の１番目のシンボル列であれば０回減算、つまり減算処理は行われない。
【００６７】
その後、シンボル列減算部１５３が、変数Ｎが元の数―１以上であるか否か判断する（ステップＳ４０５）。本実施の形態では変数Ｎが４以上であるか否かが判断される。変数Ｎが３より小さいと判断された場合（ステップＳ４０５：Ｎｏ）、シンボル列減算部１５３が、変数Ｎに対し１加算する処理を行う（ステップＳ４０６）。
【００６８】
このような減算処理を行うことで分割したシンボル列に対して、０回〜４回までのパイロットシンボル列を減算する。これにより、シンボル列（３，０，０，０）、（２，１，３，２）、（３，１，０，２）、（１，１，４，２）、（３，４，０，１）が生成される。
【００６９】
そして、シンボル列減算部１５３は、変数Ｎが４以上と判断した場合（ステップＳ４０５：Ｙｅｓ）、数値決定部１５４が、演算後のシンボル列に基づいて、準符号化シンボル列の桁毎に数値を決定する（ステップＳ４０７）。本実施の形態では、数値決定部１５４が、各桁で最も出現頻度が高い数値を、当該桁の数値として決定する。
【００７０】
具体的には、数値決定部１５４は、減算処理で得られた５個のシンボル列の１桁目で‘３’が３回と最も多く現れていることから、１桁目の数値を‘３’に決定する。当該ステップＳ４０７の処理を繰り返すことで、数値決定部１５４は、２桁目を‘１’、３桁目を‘０’、４桁目を‘２’と決定する。
【００７１】
そして、数値決定部１５４が、全ての桁について決定を行ったか否か判断する（ステップＳ４０８）。全ての桁について数値を決定していない場合（ステップＳ４０８：Ｎｏ）、ステップＳ４０７の処理を再び行う。
【００７２】
そして、数値決定部１５４が全ての桁について数値を決定した場合（ステップＳ４０８：Ｙｅｓ）、数値結合部１５５が決定した数値を結合して、準復号シンボル列を生成する（ステップＳ４０９）。これにより、準復号シンボル列として、（３，１，０，２）が得られる。
【００７３】
その後、誤り訂正符号復号部１５６が、生成した準復号シンボル列に対して、復号処理を行う（ステップＳ４１０）。本処理手順では、準復号シンボル列（３，１，０，２）を復号すると誤りなしでそのまま（３，１，０，２）が得られる。
【００７４】
次に、出力部１５７が、復号処理した復号シンボル列を出力する（ステップＳ４１１）。これにより、復号化処理装置１５０の処理が終了する。
【００７５】
図５は、復号化処理装置１５０により出力される復号シンボル列の概念を示した図である。図５に示すように、復号対象となるシンボル列を４桁毎に分割した後、シンボル列に応じてパイロットシンボル列を０回から４回繰り返して減算を行うことで、４個の演算後シンボル列を取得する。そして、４個の演算後シンボル列に基づいて、それぞれの桁毎に数値を決定して、準復号シンボル列を生成する。その後、誤り訂正を行うことで、復号シンボル列を生成する。
【００７６】
上述した処理手順においては、前提条件としてシンボル列内の‘１’及び‘２’が‘０’に誤る通信路を仮定した。この通信路の場合、シンボル列（３，１，０，２）を単純に5回繰り返し送信するだけでは、最も出現する数値に基づいて復号シンボル列を生成しても（３，０，０，０）となる。これでは、リードソロモン符号を復号できず、元の情報を得ることができない。
【００７７】
これに対して、本実施の形態においては、シンボル列の各桁に出現する元の数を一様化しているため、このような偏った誤りが生じても誤りを訂正することができる。さらに、リードソロモン符号の訂正能力を余らせている。また、本実施の形態にかかる復号化処理装置１５０の符号化・復号方式の訂正能力は、元の誤りに偏りがない場合は単純に繰り返した場合と同様となる。
【００７８】
図６は、シンボル列内の元が、他の元に遷移する確率を示した図表である。図６に格納されている変数αは、０以上０．２５以下の実数とする。図６に示す例では、０〜４のシンボルが、他のシンボルに均等の確率で遷移している。この場合では、本実施の形態にかかる処理と、従来の処理とにおいて誤り訂正が同等となる。還元すると、図６に示す例以外では、本実施の形態にかかる処理は、従来の処理と比べて誤り訂正能力が向上することになる。
【００７９】
また、本実施の形態においては、誤り訂正符号としてリードソロモン符号を用いたが、リードソロモン符号に制限するものではなく、任意の誤り訂正符号を用いることができる。また、本実施の形態のように、同期誤りが発生しない場合では、誤り訂正符号を用いなくともよい。
【００８０】
また、誤り訂正符号を用いない場合は、加算のみが定義できればよいので、加算を法演算で定義し、元の数と互いに素となる数をシンボルとしてパイロットシンボル列を構成すればよい。
【００８１】
上述した実施の形態にかかる符号化処理装置１００において、結合シンボルを生成する際に、各シンボル列の先頭と末尾を結合して一つのシンボル列を生成したが、当該結合手法に制限するものではない。つまり、符号化処理装置１００及び復号化処理装置１５０との間で、シンボルの配置情報を共有できればよく、例えば、各シンボルを任意の位置に配置して合成してもよい。
【００８２】
また、復号化処理装置１５０の数値決定部１５４において、複数のシンボル列を比較し、桁毎に最も出現している数値を、準復号シンボル列のシンボルとして決定したが、このような手法に制限するものではない。例えば、シンボル毎になんらかの信頼度情報を利用できる場合、その情報を利用してシンボルの値を決定してもよい。例えば、抽出シンボルの尤度が得られる場合は、最尤推定によりシンボルを決定する等も考えられる。
【００８３】
本実施の形態にかかる符号化処理装置１００及び復号化処理装置１５０においては、復号対象シンボル列に対して、パイロットシンボル列を繰り返し加算して元を変更しているため、所定のシンボルが変化しやすい場合であっても、高精度で復号することが可能となる。
【００８４】
また、本実施の形態は５進数の場合について説明したが、素数進数であれば、いずれの進数を使用しても良い。さらに、素数進数でない場合は、１以外の約数をもたない進数であればよい。また、それ以外の進数であっても異なる元が出るため、シンボル変化に対する耐性を向上させることはできる。
【００８５】
つまり、本実施の形態にかかる符号化処理装置１００及び復号化処理装置１５０では、符号化シンボル列中に多様な元を出現させることで、情報シンボルの偏った誤りに対してもロバストな情報抽出を可能となる。したがって、情報の復号精度を向上させることができる。
【００８６】
また、本実施の形態にかかる符号化処理装置１００では、パイロットシンボル列を線形誤り訂正符号とすることで、誤り訂正符号の符号長単位で巡回シフトしたシンボル列に対し、誤りを容易に訂正することができる符号化シンボル列を生成することができる。また、復号化処理装置１５０では、当該符号化シンボル列に対して誤り訂正符号を使用して復号することで、誤り率を小さくすることができる。
【００８７】
また、誤り訂正符号復号部１５６では、上記信頼度情報が得られる場合は軟判定復号を行ってもよい。
【００８８】
（第２の実施の形態）
第１の実施の形態においては、復号化処理装置１５０が復号対象シンボル列を入力処理する際に、同期誤りが生じない例について説明した。そこで、第２の実施の形態においては、通信路で同期誤りが発生する場合について説明する。本実施の形態にかかる同期誤りは、シンボル列が巡回する誤り、すなわち、｛ｘ（１），ｘ（２），…，ｘ（ｎ）｝が｛ｘ（ｉ），ｘ（ｉ＋１），…，ｘ（ｎ），ｘ（１），ｘ（２），…，ｘ（ｉ―１）｝のように変化する誤りを想定している。また、同期誤りと同時に、第１の実施の形態と同様に各シンボルに個別の誤りが生じているものとする。また、本実施の形態においては、シンボルが２元である場合について説明する。
【００８９】
図７は、第２の実施の形態にかかる符号化処理装置７００と復号化処理装置７５０の構成を示すブロック図である。
【００９０】
図７に示すように符号化処理装置７００の内部は、入力処理部７０１と、シンボル列加算部７０２と、シンボル列結合部７０３と、符号化シンボル列出力部７０４と、を備え、入力処理されたシンボル列Ｓ１１に対して、符号化処理を施し、復号化シンボル列Ｓ１２を出力する。なお、符号化処理装置７００の各構成が行う処理は、処理対象となるシンボルの元が５元から２元に変更された以外、第１の実施形態と異なる点がないので説明を省略する。
【００９１】
また、復号化処理装置７５０は、復号対象シンボル列入力処理部７５１と、差分算出部７５２と、桁数算出部７５３と、シフト演算部７５４と、シンボル列分割部７５５と、シンボル列減算部７５６と、数値決定部７５７と、数値結合部７５８と、誤り訂正符号復号部７５９と、パイロットシンボル列加算部７６０と、出力部７６１とを備え、入力された復号対象シンボル列Ｓ１３に対して復号化処理を施し、シンボル列Ｓ１４を出力する。
【００９２】
本実施の形態においては、シンボルはＧＦ（２）の元となる。そこで、符号化対象のシンボル列は２元７桁とする。具体的に（０，１，１，１，０，１，０）の場合について説明する。また、符号化対象シンボル列は（７，４）２元ＢＣＨ符号（生成多項式は（ｘ＾３＋ｘ＋１））で符号化されている。そして、符号化対象シンボル列の先頭から４シンボル（０，１，１，１）が情報記号とする。
【００９３】
また、同期誤りを訂正するために符号化シンボル列の所定の桁を特定の値に設定する必要がある。そこで、本実施の形態では、情報記号の先頭ビットを特定の値を常に‘０’を設定する。これにより、情報記号のうち、任意の値を設定できる情報量は３ｂｉｔとなる。
【００９４】
また、パイロットシンボル列を（１，０，１，１，０，０，０）とする。また、元が２であることから、２−１で繰り返し加算数を１とする。また、パイロットシンボル列は上記２元ＢＣＨ符号の符号語となっており、繰り返し加算数１に１加えた２回、加算を行うと零ベクトルとなる。
【００９５】
符号化の手順は第１の実施形態と同様なので、図２に従って符号化処理手順について説明する。
【００９６】
ステップＳ２０１では、入力処理部７０１が符号化対象のシンボル列（１，０，１，１，０，０，０）を入力処理する。
【００９７】
次に、シンボル列加算部７０２が、入力処理したシンボル列（１，０，１，１，０，０，０）を、加算対象に設定する（ステップＳ２０２）。そして、シンボル列加算部７０２が、加算対象のシンボル列（１，０，１，１，０，０，０）にパイロットシンボル列（１，０，１，１，０，０，０）を加算処理する（ステップＳ２０３）。当該加算処理により、（１，１，０，０，０，１，０）を生成する。
【００９８】
そして、シンボル列加算部７０２は、加算処理が元の数（２）―１回目と判断し（ステップＳ２０４：Ｙｅｓ）、シンボル列結合部７０３は、入力処理したシンボル列（１，０，１，１，０，０，０）と、加算処理した（１，１，０，０，０，１，０）とを結合して、結合シンボル（０，１，１，１，０，１，０，１，１，０，０，０，１，０）を生成する（ステップＳ２０６）。
【００９９】
そして、符号化シンボル列出力部７０４が、結合シンボル（０，１，１，１，０，１，０，１，１，０，０，０，１，０）を、符号化シンボル列として出力する（ステップＳ２０７）。次に、復号化処理装置１５０の各構成について説明する。
【０１００】
復号対象シンボル列入力処理部７５１は、復号対象シンボル列Ｓ１３の入力処理を行う。復号対象シンボル列Ｓ１３は、通信路上で誤りが生じた２進数７桁の数列とする。なお、復号対象シンボル列Ｓ１３において、同期誤りが生じていると共に、各シンボルで誤りが生じているものとする。
【０１０１】
復号対象シンボル列Ｓ１３の具体的な例としては、同期ずれとビット誤りが発生する通信路を通り、９シンボル左方向にずれて(０，０，０，１，０，０，１，１，１，０，１，０，１，１)に変化し、さらに４シンボル目に誤りが生じ(０，０，０，０，０，０，１，１，１，０，１，０，１，１)と変化したものとする。
【０１０２】
差分算出部７５２は、復号対象シンボル列Ｓ１３において、左一桁目から７桁目までのシンボル列と、８桁目から最後までのシンボル列の差分を算出する。この算出されたシンボル列を、差分シンボル列とする。つまり、差分算出部７５２は、符号化シンボル列と同じ長さの２つのシンボル列の差分を算出する。
【０１０３】
桁数算出部７５３は、差分シンボル列がパイロットシンボル列に最も近くなるようにシフト移動するための桁数を算出する。
【０１０４】
シフト演算部７５４は、算出された桁数だけ、復号対象シンボル列Ｓ１３に対してシフト演算を行う。
【０１０５】
また、復号化処理装置７５０のシンボル列分割部７５５、シンボル列減算部７５６、数値決定部７５７、数値結合部７５８、誤り訂正符号復号部７５９が行う処理は、各構成が行う処理は、処理対象となるシンボルの元が５元から２元に変更された以外、第１の実施形態と異なる点がないので説明を省略する。
【０１０６】
パイロットシンボル列加算部７６０は、誤り訂正後の準復号シンボル列の特定シンボル（先頭ビット）が特定の値（‘０’）となるように、準復号シンボル列に対してパイロットシンボル列を１又は複数回加算する。加算処理が行われた後のシンボル列が、復号シンボル列となる。そして、出力部７６１は、復号シンボル列を出力する。
【０１０７】
次に、以上のように構成された本実施の形態にかかる復号化処理装置７５０におけるシンボル列に対して符号化処理を施すまでの処理について説明する。図８は、本実施の形態にかかる復号化処理装置７５０における上述した処理の手順を示すフローチャートである。
【０１０８】
まず、復号対象シンボル列入力処理部７５１が、復号対象シンボル列の入力処理を行う（ステップＳ８０１）。
【０１０９】
次に、差分算出部７５２が、復号対象シンボル列のうち、左一桁目から符号化対象シンボル列と同じ長さ分のシンボル列と、当該シンボル列の一桁左のシンボルから符号化対象シンボル列と同じ長さ分のシンボル列と、の差分を算出する（ステップＳ８０２）。本実施の形態では、７シンボル離れた位置のシンボル同士から、差分シンボルを算出する。すなわち前半７シンボル(０，０，０，０，０，０，１)から、後半７シンボル(１，１，０，１，０，１，１)を減算し、差分シンボル列(１，１，０，１，０，１，０)を取得する。
【０１１０】
次に、桁数算出部７５３は、差分シンボル列がパイロットシンボル列に最も近くなるようにシフト移動するための桁数を算出する（ステップＳ８０３）。例えば、パイロットシンボル列は（１，０，１，１，０，０，０）であるから、上記の差分シンボル列を右方向に２シンボルシフトさせた時にハミング距離が１で最も近くなることが分かる。そこで、桁数算出部７５３は、移動桁数を右方向２シンボルと算出する。
【０１１１】
そして、シフト演算部７５４が、復号対象シンボル列Ｓ１３を、右方向に２シンボルシフトさせる演算を行い、シンボル列（１，１，０，０，０，０，０，０，１，１，１，０，１，０）を取得する（ステップＳ８０４）。
【０１１２】
その後、シンボル列分割部７５５が、当該シンボル列（１，１，０，０，０，０，０，０，１，１，１，０，１，０）を７シンボル毎に分割し、（１，１，０，０，０，０，０）、（０，１，１，１，０，１，０）を取得する（ステップＳ８０５）。
【０１１３】
そして、シンボル列減算部７５６が、変数Ｎに‘０’を設定する（ステップＳ８０６）。次に、シンボル列減算部７５６が、Ｎ＋１番目のシンボル列に対して、パイロットシンボル列をＮ回減算する処理を行う（ステップＳ８０７）。例えば、最初の１番目のシンボル列であれば０回減算、つまり減算処理は行われない。
【０１１４】
その後、シンボル列減算部７５６が、変数Ｎが元の数―１以上であるか否か判断する（ステップＳ４０５）。本実施の形態では変数Ｎが１以上であるか否かが判断される。変数Ｎが１より小さいと判断された場合（ステップＳ８０８：Ｎｏ）、シンボル列減算部７５６が、変数Ｎに対し１加算する処理を行う（ステップＳ８０９）。
【０１１５】
このような減算処理を行うことで分割したシンボル列に対して、０回〜１回までのパイロットシンボル列を減算する。これにより、シンボル列(１，１，０，０，０，０，０)、（１，１，０，０，０，１，０）が生成される。
【０１１６】
そして、シンボル列減算部７５６は、変数Ｎが１以上と判断した場合（ステップＳ８０８：Ｙｅｓ）、数値決定部７５７が、演算後のシンボル列に基づいて、準符号化シンボル列の桁毎に数値を決定する（ステップＳ８１０）。本実施の形態では、数値決定部７５７が、各桁で最も出現頻度が高い数値を、当該桁の数値として決定する。
【０１１７】
具体的には、数値決定部１５４は、これらシンボルを比較すると、６シンボル目のみが異なるので、ここを消失（*）とし、１シンボル目から順に、１，１，０，０，０，＊、０と決定する。
【０１１８】
そして、数値決定部７５７が、全ての桁について決定を行ったか否か判断する（ステップＳ８１１）。全ての桁について数値を決定していない場合（ステップＳ８１１：Ｎｏ）、ステップＳ８１０の処理を再び行う。
【０１１９】
そして、数値決定部７５７が全ての桁について数値を決定した場合（ステップＳ８１１：Ｙｅｓ）、数値結合部７５８が決定した数値を結合して、準復号シンボル列を生成する（ステップＳ８１２）。これにより、準復号シンボル列として、（１，１，０，０，０，＊、０）が得られる。
【０１２０】
その後、誤り訂正符号復号部７５９は、準復号シンボル列を復号する（ステップＳ８１３）当該準復号シンボル列（１，１，０，０，０，＊、０）を復号すると、（１，１，０，０，０，１、０）が得られる。なお、当該誤り訂正手法は、周知の手法で算出可能なので、説明を省略する。
【０１２１】
次に、パイロットシンボル列加算部７６０が、復号された準復号シンボル列（１，１，０，０，０，１、０）に対して、特定シンボルが特定の値になるようにパイロットシンボル列を加算する（ステップＳ８１４）。本実施の形態においては、上述したように先頭ビット（第１シンボル列）が‘０’となるように、加算処理を行う。そこで、パイロットシンボル列加算部７６０は、（１，１，０，０，０，１，０）にパイロットシンボル列を１回加算し、復号シンボル列（０，１，１，１，０，１，０）を生成する。
【０１２２】
その後、出力部７６１が、生成した復号シンボル列（０，１，１，１，０，１，０）を出力する（ステップＳ８１５）。
【０１２３】
本実施の形態のように、同期誤りが発生する環境下で誤り訂正符号を用いる場合、パイロットシンボル列を線形の誤り訂正符号の符号語で構成する必要がある。決定した各桁のシンボルを結合して、準復号シンボル列を生成する際に、復号されるシンボル列に二つの可能性がある。しかしながら、符号語の線形和は符号語である、という線形誤り訂正符号の性質を利用し、どちらの場合でも誤り訂正符号を復号できるようになる。
【０１２４】
この復号シンボル列の二つの可能性は、特定シンボルが特定の値になるようにパイロットシンボル列を加算することで一つに絞られる。この場合に、誤り訂正符号の復号後に特定のシンボルを得るため、この二つの候補の選択を誤る確率は誤り訂正符号の誤り率で保証されることになる。しかしながら、誤り訂正符号の誤り率は設定によって極めて小さくすることができるので、値を固定するシンボルは１つあれば十分である（そもそも誤り訂正符号で誤った場合は同期を正しく取ったとしても情報シンボルを誤るため、値を固定するシンボルを１つより大きく取る意味はない）。
【０１２５】
また、パイロットシンボル列は、上述したように復号対象シンボル列の同期に利用される。このため、巡回したパターンとの距離が十分大きくなるように設定する必要がある。なお、本実施の形態では巡回する同期誤りのみを仮定したが、その他の位置が入れ替わるような誤りが想定される場合、パイロットシンボル列を位置の入れ替わりが生じた際のシンボル列との距離が十分に大きくなるように設定する。
【０１２６】
この場合、桁数算出部７５３で、位置の入れ替わりの誤りを修正した場合の差分シンボル列とパイロットシンボル列の近さを計算する。
【０１２７】
なお、本実施の形態にかかる桁数算出部７５３において、差分シンボル列とパイロットシンボル列との近さをハミング距離で算出したが、これに制限するものではない。シンボルの信頼度情報を得られる場合、桁数算出部７５３は当該信頼度情報を用いて距離尺度を算出しても良い。差分シンボルの尤度が得られる場合、桁数算出部７５３は、最大尤度となる並べ替えを選択してもよい。誤りのタイプに事前確率を設定し、事前確率と尤度から事後確率を算出し、事後確率を最大とする並べ替えを選択してもよい。
【０１２８】
また、第１の実施の形態で示したバリエーションを、本実施の形態又は以下に示す変形例及び実施の形態に適用しても良い。
【０１２９】
本実施の形態においては、桁毎に元が異なるパイロットシンボル列を用いることで、同期誤りを訂正することが可能となる。これにより、本実施の形態にかかる符号化処理及び復号化処理は、同期用の情報を削減、又は必要とせずとも、部分的な切り取り耐性を向上させることができる。
【０１３０】
また本実施の形態においては、符号対象シンボル列において、特定のシンボルを特定の値に設定したことから、同期誤りが生じた場合でも、複数の復号シンボル列候補から、一つの復号シンボル列を特定することができる。
【０１３１】
また、上述した各実施の形態に限定されるものではなく、以下に例示するような種々の変形が可能である。
【０１３２】
（第２の実施の形態の変形例１）
上述した第２の実施の形態において、シンボルが２元の場合について説明した。しかしながら、同期誤りはシンボルが５元の場合についても適用できる。そこで、本変形例では、シンボルが５元である場合について説明する。本変形例では、シンボルが５元から２元に変更されただけなので、第２の実施の形態の符号化処理装置７００及び復号化処理装置７５０と同様の構成を備えているものとして、説明を省略する。
【０１３３】
第１の実施の形態と同様に、本変形例で使用するシンボルはＧＦ（５）の元とし、符号化対象のシンボル列（３，１，０，２）とする。符号化対象シンボル列はＧＦ（５）上のリードソロモン符号（生成多項式は（ｘ−２）＊（ｘ−４））で符号化されており、先頭シンボルは‘３’に設定する。つまり、復号対象のシンボル列のうち、情報シンボルが（３，１）であるので、任意に設定できる情報は１シンボルとなる。
【０１３４】
パイロットシンボル列は、前記リードソロモン符号の符号語である(３，４，２，１)とする。繰り返し加算数は、第１の実施の形態と同様に‘４’となる。
【０１３５】
そして、符号化処理装置７００が符号化シンボル列として、（３，１，０，２，１，０，２，３，４，４，４，４，２，３，１，０，０，２，３，１）を出力する。そして、通信路上で、符号化シンボル列に１１シンボル左にシフトする誤りが生じ、シンボル列（４，２，３，１，０，０，２，３，１，３，１，０，２，１，０，２，３，４，４，４）に変更された。さらに当該しんぼる列に対して、シンボル１と２が０になる誤りが生じ、シンボル列（４，０，３，０，０，０，０，３，０，３，０，０，０，０，０，０，３，４，４，４）に変更されたものとする。これを復号対象のシンボル列とする。
【０１３６】
次に、５元のシンボル列の対する復号化処理の手順について、図８に示したフローチャートに従って説明する。
【０１３７】
まず、復号対象シンボル列入力処理部７５１が、復号対象シンボル列（４，０，３，０，０，０，０，３，０，３，０，０，０，０，０，０，３，４，４，４）の入力処理を行う（ステップＳ８０１）。
【０１３８】
次に、差分算出部７５２が、復号対象シンボル列のうち、左一桁目から符号化対象シンボル列と同じ長さ分のシンボル列と、当該シンボル列の一桁左のシンボルから符号化対象シンボル列と同じ長さ分のシンボル列と、の差分を算出する（ステップＳ８０２）。本実施の形態では、４シンボル離れた位置のシンボル同士から、差分シンボルを算出する。すなわち左に４シンボルシフトさせた（０，０，０，３，０，３，０，０，０，０，０，０，３，４，４，４，４，０，３，０）から、復号対象のシンボルを減算し、差分シンボル（１，０，２，３，０，３，０，２，０，２，０，０，３，４，４，４，１，１，４，１）を得る。
【０１３９】
次に、桁数算出部７５３は、差分シンボル列がパイロットシンボル列に最も近くなるようにシフト移動するための桁数を算出する（Ｓ８０３）。例えば、パイロットシンボル列は（３，４，２，１）であるから、桁数算出部７５３は、これを５回繰り返した（３，４，２，１，３，４，２，１，３，４，２，１，３，４，２，１，３，４，２，１）と、上記の差分シンボルとを比較する。そして、上記の差分シンボル列を左方向に１，５，９，１３，１７シンボルシフトさせた時に、シンボルの一致数が６で最も近くなる。そこで、桁数算出部７５３は、左方向に１シンボルとシフト移動させる桁数を決定する。
【０１４０】
図９は、シフト移動させる桁数を決定するまでの概念を示した説明図である。図９に示すように、差分算出部７５２が、符号化対象シンボル列の桁数分シフト移動させた復号対象シンボル列と、復号対象シンボル列の差分から差分シンボル列を算出する。そして、桁数算出部７５３が、差分シンボル列と、パイロットシンボル列の繰り返しからなるシンボル列とを比較する。そして、左方向に１（，５，９，１３，１７）シンボルシフトさせた時に、一致度合いが最も高いと判断した場合、シフト移動させる桁数を、１（又は５，９，１３，１７）と決定する。
【０１４１】
図８に戻り、シフト演算部７５４が、復号対象シンボル列を左方向に1シンボルシフトさせ、シンボル列（０，３，０，０，０，０，３，０，３，０，０，０，０，０，０，３，４，４，４，４）を算出する。なお、本処理手順では、１シンボル左にシフトさせたが、５，９，１３，１７シンボル左にシフトさせてもよい。
【０１４２】
次に、シンボル列分割部７５５が、シンボルシフト後のシンボル列を４シンボル毎に分割し、（０，３，０，０)、(０，０，３，０)、(３，０，０，０)、(０，０，０，３)、(４，４，４，４)を得る。
【０１４３】
そして、シンボル列減算部７５６が、変数Ｎに‘０’を設定する（ステップＳ８０６）。次に、シンボル列減算部７５６が、Ｎ＋１番目のシンボル列に対して、パイロットシンボル列をＮ回減算する処理を行う（ステップＳ８０７）。例えば、最初の１番目のシンボル列であれば０回減算、つまり減算処理は行われない。
【０１４４】
その後、シンボル列減算部７５６が、変数Ｎが元の数―１以上であるか否か判断する（ステップＳ４０５）。本変形例では変数Ｎが４以上であるか否かが判断される。変数Ｎが４より小さいと判断された場合（ステップＳ８０８：Ｎｏ）、シンボル列減算部７５６が、変数Ｎに対し１加算する処理を行う（ステップＳ８０９）。
【０１４５】
このような減算処理を行うことで分割したシンボル列に対して、０回〜４回までのパイロットシンボル列を減算する。これにより、シンボル列(０，３，０，０)、(２，１，１，４)、(２，２，１，３)、(１，３，４，０)、(２，３，１，０)が生成される。
【０１４６】
そして、シンボル列減算部７５６は、変数Ｎが４以上と判断した場合（ステップＳ８０８：Ｙｅｓ）、数値決定部７５７が、演算後のシンボル列に基づいて、準符号化シンボル列の桁毎に数値を決定する（ステップＳ８１０）。本実施の形態では、数値決定部７５７が、各桁で最も出現頻度が高い数値を、当該桁の数値として決定する。これにより、数値決定部７５７は、それぞれの桁毎に数値２，３，１，０を決定する。
【０１４７】
そして、数値決定部７５７が、全ての桁について決定を行ったか否か判断する（ステップＳ８１１）。全ての桁について数値を決定していない場合（ステップＳ８１１：Ｎｏ）、ステップＳ８１０の処理を再び行う。
【０１４８】
そして、数値決定部７５７が全ての桁について数値を決定した場合（ステップＳ８１１：Ｙｅｓ）、数値結合部７５８が決定した数値を結合して、準復号シンボル列を生成する（ステップＳ８１２）。これにより、準復号シンボル列（２，３，１，０）が生成される。
【０１４９】
その後、誤り訂正符号復号部７５９は、準復号シンボル列を復号する（ステップＳ８１３）当該準復号シンボル列（２，３，１，０）を復号し、誤り無しで（２，３，１，０）を取得する。
【０１５０】
次に、パイロットシンボル列加算部７６０が、復号された準復号シンボル列（２，３，１，０）に対して、特定シンボルが特定の値になるようにパイロットシンボル列を加算する（ステップＳ８１４）。本変形例においては、上述したように先頭シンボルが‘３’になるように、パイロットシンボル列を加算する。
【０１５１】
そこで、パイロットシンボル列加算部７６０が、復号された準復号シンボル列（２，３，１，０）に対してパイロットシンボル列を２回加算し、復号シンボル列（３，１，０，２）を生成する（ステップＳ８１５）。
【０１５２】
図１０は、復号対象シンボル列から復号シンボル列を生成するまでの概念を示した説明図である。図１０に示すように、上述した処理で決定した桁数（例えば１桁）だけシンボル列をシフト移動させた後、第１の実施の形態と同様に４桁ごとに分割する。そして、分割されたそれぞれのシンボル列に対してパイロットシンボル列による減算処理を行う。減算回数は０回〜４回とする。このように減算処理により生成された複数のシンボル列から、準復号シンボル列を生成する。そして、生成された準復号シンボル列に対して、誤り訂正を行った後、特定シンボルが特定の値になるようにパイロットシンボル列を加算して、復号シンボル列を生成する。
【０１５３】
本変形例では５元の場合について説明したが、当然に他の元でも良い。そして、上述した符号化処理及び復号化処理を用いた場合、元の数に拘わらず、同期誤り及びシンボル誤りを訂正することができる。
【０１５４】
本変形例では、パイロットシンボル列が５（元の数）回加算して零ベクトルになることから、巡回シフトしたシンボル列の同期を取れる符号化シンボル列を生成していることになる。これにより、同期誤りを訂正することが可能となる。
【０１５５】
（第２の実施の形態の変形例２）
上述した実施の形態及び変形例では、誤り符号訂正としてリードソロモン符号を用いた。しかしながら、誤り符号訂正は、周知を問わずあらゆる符号訂正を用いることができる。そこで、本変形例では、短縮化符号を使用した場合について説明する。
【０１５６】
まず、本変形例ではシンボルは２元とし、短縮化符号として(７，４)２元ＢＣＨ符号（生成多項式は(ｘ＾３＋ｘ＋１）の先頭の情報記号を０に固定した短縮化(６，３)２元ＢＣＨ符号を用いる。
【０１５７】
符号化対象のシンボル列を(１，１，１，０，１，０)、パイロットシンボル列を(０，１，１，０，０，０)とし、繰り返し加算数を１とする。本変形例では、パイロットシンボル列の先頭に０以外のシンボルを追加した基本パイロットシンボル列を用いるとともに、(７，４)２元ＢＣＨ符号の符号語となるよう設定する。ここでは基本パイロットシンボル列を(１，０，１，１，０，０，０)とする。
【０１５８】
また、本実施例では、基本となる(７，４)２元ＢＣＨ符号のうち１シンボルを固定しているが、符号化対象シンボル列内に固定シンボルを設けたわけではない。このため、本実施例では同期による情報のロスを抑止することができる。
【０１５９】
符号化は第２の実施の形態と同様の処理とする。そして、符号化処理装置７００が、シンボル列（１，１，１，０，１，０)を符号化することで、符号化シンボル列（１，１，１，０，１，０，１，０，０，０，１，０)を生成する。
【０１６０】
復号処理手順は図８に示す処理手順のうち、ステップＳ８１３において誤り訂正符号の復号方法が変更される。
【０１６１】
まず、ステップＳ８１２までで準復号シンボル列(１，０，０，０，１，０)が得られたものとする。ここで先頭に１シンボル追加し、そこを消失とし(*，１，０，０，０，１，０)とする。誤り訂正符号復号部１５６が消失訂正を行い、準復号シンボル列(１，１，０，０，０，１，０)を取得する。
【０１６２】
その後、パイロットシンボル列加算部７６０は、短縮化部分のシンボルの値が特定の値となるように、基本パイロットシンボル列を加える（ステップＳ８１５）。その後、出力部７６１が、基本パイロットシンボル列加算後のシンボル列から、短縮化部分を除去し、復号シンボル列を取得する。
【０１６３】
具体例には、先頭の情報記号を０に固定しているので、パイロットシンボル列加算部７６０は、基本パイロットシンボル列を１回加算し、シンボル列(０，１，１，１，０，１，０)を取得する。その後、短縮化部分である先頭1シンボルを削除し、復号シンボル列(１，１，１，０，１，０)を取得する。
【０１６４】
本変形例では、２元の場合について説明したが、それ以外の場合についても当然に適用することができる。
【０１６５】
本変形例では、同期情報を符号化対象シンボル列に含めないで済むため、情報の格納量が増加させることができる。その代わり、誤り訂正符号の消失訂正能力を1つ使用することとなる。本変形例は、符号長を短縮化する必要がある場合に有用である。
【０１６６】
つまり、本変形例では、短縮化部分のシンボルを使うことで、情報シンボルの損失なくシンボル列（情報）を同期させることができる。
【０１６７】
（第２の実施の形態の変形例３）
第２の実施の形態及び第２の実施の形態の変形例２で示したようにシンボル列が２元の場合、元の出現確率が均等になっていない。２元の場合、元の出現確率を均等にするにはパイロットシンボル列の全てのシンボルが１のものを使用する必要がある。しかしながら、全てのシンボルが１のシンボル列を使用した場合、同期誤りを訂正することができない。そこで、本変形例では、元の出現確率の均等化及び情報同期を行う方法として、シンボル列の符号化処理及び復号化処理を階層的に適用する例について説明する。
【０１６８】
本変形例にかかる符号化処理装置では、パイロットシンボル列Ａと、シンボル全てが１のシンボル列Ｂを予め保持しておく。そして、符号化処理装置が符号化対象シンボル列Ｘを入力処理した場合、符号化シンボル列としてシンボル列｛Ｘ，Ｘ＋Ａ，Ｘ＋Ｂ，Ｘ＋Ａ＋Ｂ｝を生成する。
【０１６９】
そして、復号化処理装置が、復号対象シンボル列｛Ｘ，Ｘ＋Ａ，Ｘ＋Ｂ，Ｘ＋Ａ＋Ｂ｝を入力処理する。復号対象シンボル列の長さをｎとした場合、復号化処理装置は、当該復号対象シンボル列に含まれるシンボル列のうち、２ｎシンボル離れた位置のシンボル列間の差分を算出し、当該差分シンボル列においてｎシンボル離れた位置のシンボル列間の差分を算出する。当該算出された差分とｆ（Ａ）＋ｇ（ｆ（Ｂ，０））との距離が最小になるようにｆを算出する。このｆは、シンボル列を巡回シフトさせる演算子である。また、ｇは先頭nシンボルを取得する演算子である。復号対象シンボル列に対して、算出されたfを用いてシンボルシフトを行うことで、同期誤りを訂正する。他の処理は、上述した実施の形態及び変形例で説明した復号の処理手順と同様として説明を省略する。
【０１７０】
（第３の実施の形態）
上述した符号化処理及び復号化処理はさまざまな処理に適用することが出来る。そこで、本実施の形態においては、符号化処理及び復号化処理を、電子透かしに適用した例について説明する。
【０１７１】
図１１は、第３の実施の形態にかかる電子透かし埋込装置１１００及び電子透かし抽出装置１１５０の構成を示すブロック図である。電子透かし埋込装置１１００は、上述した第２の実施の形態にかかる符号化処理装置７００とは、符号化シンボル列出力部１０４が削除され、画像埋込部１１０１及び画像出力部１１０２が追加されている点で異なる。
【０１７２】
また、電子透かし抽出装置１１５０は、上述した第２の実施の形態にかかる復号化処理装置７５０とは、復号対象シンボル列入力処理部１５１が削除され、画像入力処理部１１５１及び符号化シンボル列抽出部１１５２とが追加された点で異なる。以下の説明では、上述した第２の実施の形態と同一の構成要素には同一の符号を付してその説明を省略している。
【０１７３】
ところで、電子透かしにおいては、電子透かしでは強く情報を埋め込むとコンテンツが劣化するため、微弱な信号を分散させて埋め込むことが有用である。パッチワーク法はその主たるものであり、１シンボルに対して複数の特徴量を割り当てその値を変更することで情報を埋め込む。そして、１シンボルに割り当てられた複数の特徴量の偏りから情報を抽出する。また、コンテンツの分割に対して耐性を持たせるため、繰り返し情報が埋め込むことが一般に行われる。そして、本実施の形態にかかる符号化処理及び復号化処理は、「微弱な信号」を「繰り返す」ことが要求される場合に好適である。
【０１７４】
次に電子透かし埋込装置１１００について説明する。画像埋込部１１０１は、画像データに対して、シンボル列結合部７０３により生成された符号化シンボル列を埋め込む処理を行う。この符号化シンボル列は、透かし情報に対して符号化を行ったものとする。なお、画像データに対して、符号化シンボル列を埋め込む手法は、周知の手法を問わず、あらゆる手法を用いることができる。画像出力部１１０２は、符号化シンボル列が埋め込まれた画像データを出力する。
【０１７５】
このようにして出力された符号化シンボル列が埋め込まれた画像データを、電子透かし抽出装置１１５０が入力処理を行う。そこで、次に電子透かし抽出装置１１５０について説明する。
【０１７６】
画像入力処理部１１５１は、符号化シンボル列が埋め込まれた画像データの入力処理を行う。そして、符号化シンボル列抽出部１１５２は、入力処理された画像データから、符号化シンボル列の抽出処理を行う。この抽出手法については、周知の手法を問わず、あらゆる手法を用いることができる。
【０１７７】
また、符号化シンボル列抽出部１１５２は、符号化シンボル列の他に、画像データに埋め込まれた信頼度情報等を抽出することにしても良い。この場合、抽出された信頼度情報を用いて、復号化処理が行われることになる。
【０１７８】
そして、抽出処理された符号化シンボル列の復号化処理については、第２の実施の形態と同じものとして説明を省略する。
【０１７９】
図１１は、上述した実施の形態及び変形例で示した符号化処理装置及び復号化処理装置の機能を実現するためのプログラムを実行したＰＣのハードウェア構成を示した図である。本実施の形態の符号化処理装置及び復号化処理装置は、ＣＰＵ（Central Processing Unit）５１等の制御装置と、ＲＯＭ（Read Only Memory）５２やＲＡＭ（Random Access Memory）５３等の記憶装置と、通信Ｉ／Ｆ５７と、これらを接続するバス６２を備えており、通常のコンピュータを利用したハードウェア構成となっている。
【０１８０】
上述した実施形態及び変形例の符号化処理装置で実行される符号化処理プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０１８１】
また、上述した実施形態及び変形例の復号化処理装置で実行される復号化処理プログラムも、同様にインストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０１８２】
また、上述した実施形態及び変形例の復号化処理装置で実行される復号化処理プログラム、及び復号化処理装置で実行される復号化処理プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、上述した実施形態及び変形例の復号化処理プログラム、及び復号化処理プログラムをインターネット等のネットワーク経由で提供または配布するように構成しても良い。
【０１８３】
また、上述した実施形態及び変形例の復号化処理プログラム、及び復号化処理プログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０１８４】
上述した実施形態及び変形例の復号化処理プログラム、及び復号化処理プログラムは、符号化処理装置又は復号化処理装置において上記記録媒体から読み出して実行することによりＲＡＭ５３上にロードされ、上記ソフトウェア構成で説明した各部がＲＡＭ５３上に生成されるようになっている。
【０１８５】
なお、電子透かし埋込装置及び電子透かし抽出装置も、符号化処理装置及び復号化処理装置と同様の構成を備えているものとして説明を省略する。
【産業上の利用可能性】
【０１８６】
以上のように、本発明にかかる符号化処理装置、符号化処理方法、符号化処理プログラムは、符号化した情報を正確に抽出する技術として有用であり、特に、電子透かしとして埋込む技術に適している。
【図面の簡単な説明】
【０１８７】
【図１】第１の実施の形態にかかる符号化処理装置と復号化処理装置の構成を示すブロック図である。
【図２】第１の実施の形態にかかる符号化処理装置におけるシンボル列に対して符号化処理を施すまでの処理手順を示すフローチャートである。
【図３】第１の実施の形態にかかる符号化処理装置により出力される符号化シンボル列の概念を示した図である。
【図４】第１の実施の形態にかかる復号化処理装置におけるシンボル列に対して復号化処理を施すまでの処理手順を示すフローチャートである。
【図５】第１の実施の形態にかかる復号化処理装置により出力される復号シンボル列の概念を示した図である。
【図６】シンボル列内の元が、他の元に遷移する確率を示した図表である。
【図７】第２の実施の形態にかかる符号化処理装置と復号化処理装置の構成を示すブロック図である。
【図８】第２の実施の形態にかかる復号化処理装置におけるシンボル列に対して復号化処理を施すまでの処理手順を示すフローチャートである。
【図９】シフト移動させる桁数を決定するまでの概念を示した説明図である。
【図１０】復号対象シンボル列から復号シンボル列を生成するまでの概念を示した説明図である。
【図１１】第３の実施の形態にかかる電子透かし埋込装置及び電子透かし抽出装置の構成を示すブロック図である。
【図１２】符号化処理装置及び復号化処理装置の機能を実現するためのプログラムを実行したＰＣのハードウェア構成を示した図である。
【符号の説明】
【０１８８】
５１  ＣＰＵ
５２  ＲＯＭ
５３  ＲＡＭ
５７  通信Ｉ／Ｆ
６２  バス
１００、７００  符号化処理装置
１０１、７０１  入力処理部
１０２、７０２  シンボル列加算部
１０３、７０３  シンボル列結合部
１０４、７０４  符号化シンボル列出力部
１５０、７５０  復号化処理装置
１５１、７５１  復号対象シンボル列入力処理部
１５２、７５５  シンボル列分割部
１５３、７５６  シンボル列減算部
１５４、７５７  数値決定部
１５５、７５８  数値結合部
１５６、７５９  訂正符号復号部
１５７、７６１  出力部
７５２  差分算出部
７５３  桁数算出部
７５４  シフト演算部
７６０  パイロットシンボル列加算部
１１００  電子透かし埋込装置
１１０１  画像埋込部
１１０２  画像出力部
１１５０  電子透かし抽出装置
１１５１  画像入力処理部
１１５２  符号化シンボル列抽出部
【図１】
0004799514.tif 000002
【図２】
0004799514.tif 000003
【図３】
0004799514.tif 000004
【図４】
0004799514.tif 000005
【図５】
0004799514.tif 000006
【図６】
0004799514.tif 000007
【図７】
0004799514.tif 000008
【図８】
0004799514.tif 000009
【図９】
0004799514.tif 000010
【図１０】
0004799514.tif 000011
【図１１】
0004799514.tif 000012
【図１２】
0004799514.tif 000013