• ポートフォリオ機能


ポートフォリオを新規に作成して保存
既存のポートフォリオに追加保存

  • この表をプリントする
PDF PDFをダウンロード
審決分類 審判 査定不服 (159条1項、163条1項、174条1項で準用) 特許、登録しない。 H03M
審判 査定不服 2項進歩性 特許、登録しない。 H03M
管理番号 1115581
審判番号 不服2002-5161  
総通号数 66 
発行国 日本国特許庁(JP) 
公報種別 特許審決公報 
発行日 2000-07-28 
種別 拒絶査定不服の審決 
審判請求日 2002-03-27 
確定日 2005-04-21 
事件の表示 平成11年特許願第 4602号「リード・ソロモン復号器及び誤り訂正方法」拒絶査定不服審判事件〔平成12年 7月28日出願公開、特開2000-209101〕について、次のとおり審決する。 
結論 本件審判の請求は、成り立たない。 
理由 1.手続の経緯
本願は、平成11年1月11日の出願であって、平成14年2月22日付けで拒絶査定がなされ、これに対し、平成14年3月27日に拒絶査定に対する審判請求がなされるとともに平成14年4月4日付けで手続補正がなされたものである。

2.平成14年4月4日付けの手続補正について
[結論]
平成14年4月4日付けの手続補正を却下する。

[理由]
(1)補正の適否
本件補正は、例えば、特許請求の範囲の請求項7を、
「【請求項7】前記Λ・Ω商ROMは、前記パラレルシンドローム情報をアドレスに見立て、予め計算しメモリに格納されていた前記誤り位置多項式情報及び/または前記誤り評価多項式情報を出力するように構成されていることを特徴とする請求項5に記載のリード・ソロモン復号器。」
と補正することを含むものである。
しかしながら、補正前の請求項7は、請求項6を引用しており、補正後の請求項7は、請求項5を引用しているので、補正後の請求項7は、請求項6に記載された発明に特定すべき事項である「【請求項6】 前記シンボルS/P変換回路は、前記シンドローム計算回路からシリアルで出力されてくる32シンボル構成の前記シンドローム情報を、前記シンボルS/P変換回路により所定シンボル数のパラレルシンドローム情報に変換するように構成されていることを特徴とする請求項5に記載のリード・ソロモン復号器。」が削除されており、上記補正は、特許法17条の2第4項第1号ないし第4号のいずれの目的にも適合しない。

(2)むすび
以上のとおり、本件補正は、特許法第17条の2第4項第1号ないし第4号の規定のいずれにも適合しないから、特許法第159条第1項で準用する特許法第53条第1項の規定により却下されるべきものである。

3.本願発明について
(1)本願発明
平成14年4月4日付けの手続補正は上記のとおり却下されたので、本願の請求項1に係る発明(以下、「本願発明」という。)は、平成14年1月25日付け手続補正書の特許請求の範囲の請求項1に記載された事項により特定される、以下のとおりのものである。

「【請求項1】 ガロア体GFを使用するリード・ソロモン復号器において、
符号化データのシンドローム情報を計算するシンドローム計算回路と、
前記シンドローム情報からユークリッド・アルゴリズムによる誤り位置多項式情報及び/または誤り評価多項式情報を計算するΛ・Ω計算回路と、
前記誤り位置多項式情報から誤り位置の情報を計算する誤り位置計算回路と、
前記誤り位置多項式情報と前記誤り評価多項式情報とから誤り量の情報を計算する誤り量計算回路と、
前記符号化データ情報と前記誤り位置情報と前記誤り量情報とから訂正情報を出力する受信符号語修正回路と、
前記シンドローム計算回路により算出された前記シンドローム情報に対して32次多項式割り算を実行して商計算入力分母情報及び/または商計算入力分子情報を生成する誤り評価多項式計算回路と、
ユークリッド・アルゴリズムで使用する商の計算を予め格納するとともに、ユークリッド・アルゴリズムにおける割り算を実行する際に当該割り算の実行に代えて当該割り算に応じた商を前記格納された商の中から選択して出力するとともに、前記ユークリッド・アルゴリズムで使用する商の計算を予め格納する際、前記商計算入力分母情報及び前記商計算入力分子情報をアドレスに見立て、当該アドレスに対して予め計算された商のデータを格納する商ROMとを有することを特徴とするリード・ソロモン復号器。」

(2)引用例に記載された発明
原審の拒絶の理由に引用された特開平10-135846号公報(以下、「引用例1」という。)には、以下の事項が記載されている。
イ)「【請求項1】 t重誤り訂正リードソロモン符号よりなる受信多項式Y(z) からシンドローム多項式S(z) を求めるための第1のユニットと、
ユークリッド互除演算によって前記シンドローム多項式S(z) から誤り位置多項式σ(z) と誤り評価多項式ω(z) とを求め、かつk(k≦t)個の誤り評価値を対応する誤り位置多項式微分値で除算することによってk個の誤りの値eu を求めるための第2のユニットと、
チェン探索によって前記誤り位置多項式σ(z) のk個の根α-ju を求め、かつ前記誤り評価多項式ω(z) に前記k個の根α-ju をそれぞれ代入して得られる誤り評価値と、前記誤り位置多項式σ(z) の導関数に前記k個の根α-ju をそれぞれ代入して得られる誤り位置多項式微分値とを前記第2のユニットへ供給するための第3のユニットと、
前記k個の根α-ju からk個の誤り位置を求め、かつ前記受信多項式Y(z) の中の対応位置から前記k個の誤りの値eu のうちの対応する誤りの値をそれぞれ差し引くことによって、誤り訂正された多項式W(z) を求めるための第4のユニットとを備え、
前記第1のユニットは1つのパケットサイクルに対応する第1のパイプラインステージを、前記第2及び第3のユニットは次のパケットサイクルに対応する第2のパイプラインステージを、前記第4のユニットは更に次のパケットサイクルに対応する第3のパイプラインステージをそれぞれ構成することを特徴とするリードソロモン復号器。」(第2頁第1欄第2行〜第28行)

ロ)「【0002】
【従来の技術】各種大容量記憶装置の記憶情報、高速通信の伝送情報等において、多重誤り訂正を可能とする符号としてリードソロモン符号が広く使用されている。
【0003】リードソロモン符号は、原始多項式をW(z) とし、W(z) =0の根をαとするとき、この根αを原始元とするガロア体(Galois field)の上の符号であって、ブロック誤り訂正符号の1つである。ここで、αをガロア体GF(2m )の原始元とし、α,α2 ,…,α2tを根とする符号長n=2m -1のリードソロモン符号を考える。この符号によれば、mビットが1処理単位すなわち1シンボルとされる。原情報の量はn-2tシンボルである。以下の説明ではm=8とし、1シンボルが8ビットすなわち1バイトで表わされるものとする。1パケットの受信語は、n個のシンボルからなる。t=8の場合には8シンボルの誤り訂正が可能である。
【0004】リードソロモン符号の復号は、次のステップ(i) 〜(vi)による。ただし、ステップ(iii) 〜(v) において不合理な結果を生じる場合には、訂正不可能な誤りが生じたと判定する。
【0005】
(i) 受信語中の各シンボルを係数とする受信多項式Y(z) から、
si =Y (αi ) …(1)
により、2t個のシンドローム(syndrome)、すなわちs1 ,s2 ,…,s2tを計算する。各シンドロームsi はガロア体GF(2m )の元である。シンドローム多項式S(z) は、
S(z) =s1 +s2 z+…+s2tz2t-1 …(2)
で定義される。
【0006】
(ii) シンドロームが全て零であれば、誤りなしと判定する。
【0007】
(iii) シンドローム中に非零のものがあれば、シンドローム多項式S(z) から、誤り位置多項式(error locator polynomial)σ(z) と、誤り評価多項式(error evaluator polynomial)ω(z) とを求める。具体的には、φ(z) を多項式とするとき、
φ(z) z2t+σ(z) S(z) =ω(z) …(3)
σ(0) =1 …(4)
を満たし、かつ互いに素であるt次以下の多項式σ(z) と、t-1次以下の多項式ω(z) とを求める。
【0008】
(iv) σ(z) =0のk(k≦t)個の根α-ju (ju =j1 ,j2 ,…,jk )を求める。ここに、kは誤り位置多項式σ(z) の次数であって、誤りの個数を表わしている。σ(z) にα-i(i=0,1,…,n)を個々に代入し、σ (α-i) が零かどうかを調べる方法を採用すれば、全ての根を探索できる。この方法はチェン探索(Chien search)と呼ばれる。なお、k個の根α-ju の各々は、いわゆる誤りロケータ(error locator )の逆数である。
【0009】
(v) 誤り位置多項式σ(z) の導関数すなわちσ'(z)を求め、
eu =-ω (α-ju ) /σ'(α-ju ) …(5)
から、誤りの値e1 ,e2 ,…,ek を求める。ここに、ω (α-ju ) を誤り評価値といい、σ'(α-ju ) を誤り位置多項式微分値という。
【0010】
(vi) k個の根α-j1 ,α-j2 ,…,α-jk から誤りの位置j1 ,j2 ,…,jk を求め、受信語中のこれらの位置のシンボルからそれぞれ誤りの値e1 ,e2 ,…,ek を差し引くことによって、受信語中の誤りを訂正する。
【0011】
上記ステップ(iii) において誤り位置多項式σ(z) と誤り評価多項式ω(z) とを求める方法の1つとして、ユークリッド法(Euclid's algorithm)が知られている。ユークリッド法は、z2tとS(z) との最大公約多項式をユークリッド互除演算で算出することによって、σ(z) とω(z) とを求めるものである。」(第2頁第2欄第28行〜第3頁第4欄第24行)

ハ)「【0022】
【発明の実施の形態】

図1は、本発明に係るリードソロモン復号器の構成を示している。図1のリードソロモン復号器は、シンドローム計算ユニット101と、ユークリッド互除演算及び誤り値計算ユニット102と、チェン探索ユニット103と、データ遅延用RAM104と、誤り訂正ユニット105とを備えたものである。シンドローム計算ユニット101は、t重誤り訂正リードソロモン符号よりなる受信多項式Y(z) から、式(2)で定義されるシンドローム多項式S(z) を求める。具体的には、受信多項式Y(z) は受信語中の各シンボルを係数とする多項式である。この受信多項式Y(z) から、式(1)により2t個のシンドローム、すなわちs1 ,s2 ,…,s2tが計算される。2t個のシンドロームが全て零であれば、誤りなしとの判定を誤り訂正ユニット105が下す。ユークリッド互除演算及び誤り値計算ユニット102は、ユークリッド互除演算の改良されたアルゴリズムに従って、シンドローム多項式S(z) から誤り位置多項式σ(z) と誤り評価多項式ω(z) とを求める。具体的には、式(3)及び(4)を満たし、かつ互いに素であるt次以下の多項式σ(z) と、t-1次以下の多項式ω(z) とを求める。このユニット102は、チェン探索ユニット103から各々k(k≦t)個の誤り評価値ω (α-ju ) と誤り位置多項式微分値σ'(α-ju ) との供給を受け、式(5)によりk個の誤りの値eu 、すなわちe1 ,e2 ,…,ek を求める機能をも有する。チェン探索ユニット103は、σ(z) =0のk個の根α-ju (ju =j1 ,j2 ,…,jk )を求め、該求めたk個の根α-ju を誤り訂正ユニット105へ供給する。このユニット103は、誤り評価多項式ω(z) に該k個の根α-juをそれぞれ代入して得られる誤り評価値ω (α-ju ) と、誤り位置多項式σ(z) の導関数σ'(z)に該k個の根α-ju をそれぞれ代入して得られる誤り位置多項式微分値σ'(α-ju ) とをユークリッド互除演算及び誤り値計算ユニット102へ供給する機能をも有する。データ遅延用RAM104は、受信多項式Y(z) を2パケットサイクルだけ遅延させるものである。誤り訂正ユニット105は、チェン探索ユニット103から供給されたk個の根α-ju に基づいて誤りの位置j1 ,j2 ,…,jk を求め、データ遅延用RAM104から供給された受信多項式Y(z) の中のこれらの位置のシンボルからそれぞれ誤りの値e1 ,e2 ,…,ek を差し引くことによって受信語中の誤りを訂正し、かつその結果である誤り訂正された多項式W(z) を出力する。」(第4頁第6欄第36行〜第5頁第7欄第29行)

以上の記載及び図1を総合すると、引用例には、「ガロア体GFを使用するリードソロモン復号器において、
t重誤り訂正リードソロモン符号よりなる受信多項式のシンドローム多項式を計算するシンドローム計算ユニットと、
前記シンドローム多項式からユークリッド互除演算による誤り位置多項式及び誤り評価多項式を計算するユークリッド互除演算及び誤り値計算ユニットと、
前記誤り位置多項式から誤り位置を求め、
前記誤り位置多項式と前記誤り評価多項式とから誤りの値を計算し、
前記受信多項式と前記誤り位置と前記誤りの値とから誤り訂正された多項式を求める誤り訂正ユニットと、
前記シンドローム計算ユニットにより算出された前記シンドローム多項式に対して、ユークリッド互除演算を行うリードソロモン復号器」の発明(以下、「引用例に記載された発明」という。)が記載されている。

例えば、特開昭62-69728号公報(以下、「周知例1」という。)には、以下の事項が記載されている。

イ)「実施例
第1図は本発明の一実施例による復号化処理回路の概略構成を示すものであって、12は符号化コード1からシンドロームを計算するシンドローム計算回路、13はシンドロームから誤りの位置を計算する誤り位置計算回路、14はシンドロームと誤り位置情報とから誤りの大きさを計算する誤り大きさ計算回路、15は符号化コード1と誤り位置情報と誤り大きさ情報とから対応する情報コードを出力して誤りを訂正する回路、16は誤り位置計算回路13と誤り大きさ計算回路14のどちらかが乗算器17を使用するのかを切り換えるセレクタ、18は除算処理の際に逆元を出力するROM、19は乗算処理と除算処理によって乗算器の入力を切り換えるセレクタである。
以上のように構成された誤り訂正回路について、以下その動作を説明する。情報記憶装置等によって誤りの生じた符号化コード1が入力されると、シンドローム計算回路12によって、生じた誤りに依存したシンドローム情報が算出され、このシンドローム情報を基にして以下の復号化処理が行われることになる。次に、算出されたシンドローム情報のみから誤り位置計算回路13によって誤っている位置を表わす情報が算出され、誤り大きさ計算回路14へ入力される。この誤り大きさ計算回路14ではシンドローム情報と誤り位置情報とから誤りの大きさを表わす情報が算出される。この誤り位置計算回路13及び誤り大きさ計算回路14で行なわれる演算処理には、ガロア体上(GF(2n)上)の元の加算処理、乗算処理、除算処理が必要となるが、加算処理については非常に容易な回路で実現されるために誤り位置計算回路13と誤り大きさ計算回路14の双方に加算回路を内蔵している。乗算処理及び除算処理を行なうために、セレクタ16、19、逆元ROM18、乗算器17が必要となる。乗算処理の場合は、誤り位置計算回路13及び誤り大きさ計算回路14から出力された情報はセレクタ16,セレクタ19を通過してそのまま乗算器13に入力され乗算処理が行なわれ、その結果が誤り位置計算回路13及び誤り大きさ計算回路14にもどされてくる。除算処理の場合は逆元の乗算という形で実現され、誤り位置計算回路13及び誤り計算回路14から出力された情報はセレクタ16を通過したのち逆元ROM18に入力され、その出力が乗算器17に入力されることによって除算処理が行なわれる。誤り大きさ計算回路14の処理は誤り位置計算回路13の処理が終了してから行なわれるものなので、セレクタ16、19、逆元ROM18、乗算器17を誤り位置計算回路13と誤り大きさ計算回路14とが同時に使用するという状態は起こらない。以上の処理によって誤り位置情報と誤り大きさ情報が算出され訂正回路15に入力されると、符号化コード1の誤りは誤り位置情報と誤り大きさ情報を基にして訂正され情報コードとして出力される。」(第2頁右上欄第18行〜第3頁左上欄第12行)

上記周知例1によれば、「誤り位置計算回路や誤り大きさ計算回路における多項式除算を行うのに、逆元ROMと乗算手段を用いて行う」ことは周知である。

例えば、特開平5-244016号公報(以下、「周知例2」という。)には、次の事項が記載されている。

イ)「【請求項1】 一連のデータ列をn次(nは正の整数)の多項式f(x)で表わし、該多項式f(x)をm次(mは正の整数)の基本式P(x)で除算した剰余r(x)をCRC符号として生成するCRC計算回路において、前記多項式f(x)の上位k項(kはk<nの正の整数)が取り得る全ての式を前記基本式P(x)で除算した各剰余が記録されたメモリと、前記多項式f(x)の上位k項に付加された各係数に基づいて前記メモリのアドレスを指定し対応する剰余を読み出すアクセス手段と、このアクセス手段で読み出された剰余を前記多項式f(x)の上位k項を除く下位項に加算する加算手段とを具備してなることを特徴とするCRC計算回路。」(第2頁第1欄第2行〜第14行)

例えば、特開平10-215187号公報(以下、「周知例3」という。)には、次の事項が記載されている。

イ)「【0027】ブロック演算手段3-1,3-2内でのメモリ22の構成例を、図4,5を用いて説明する。図4は、x20からx23までの次数を持つ符号多項式を生成多項式G(x) で除算した演算結果(剰余)の記憶状態を表示し、図5は、x16からx19までの次数を持つ符号多項式を生成多項式G(x) で除算した演算結果(剰余)の記憶状態を表示したものである。各メモリ22では、符号多項式の係数ビットをアドレスとし、このアドレスに対応して、該当する符号多項式をG(x) で除算した演算結果(剰余)が保持されている。」(第8頁第13欄第35行〜第44行)

周知例2、3によれば、「多項式を多項式で割る除算の剰余を求めるのに、剰余が記録されたメモリを係数に基づいたアドレスで読み出すことにより、剰余を出力する」ことが周知である。

(3)対比・判断
本願発明と引用例に記載された発明を比較する。
引用例に記載された発明の「リードソロモン復号器」は、本願発明の「リード・ソロモン復号器」に相当する。
引用例に記載された発明の「t重誤り訂正リードソロモン符号よりなる受信多項式」は、誤り訂正符号化されたデータであるから、本願発明の「符号化データ」に相当する。
引用例に記載された発明の「シンドローム多項式」は、情報であるから、本願発明の「シンドローム情報」に相当する。
引用例に記載された発明の「シンドローム計算ユニット」は、回路により構成されるから、「シンドローム計算回路」に相当する。
引用例に記載された発明の「ユークリッド互除演算」は、ユークリッドアルゴリズムであるから、本願発明の「ユークリッド・アルゴリズム」に相当する。
引用例に記載された発明の「誤り位置多項式」、「誤り評価多項式」は、共に情報であるから、「誤り位置多項式情報」、「誤り評価多項式情報」に相当する。
引用例に記載された発明の「ユークリッド互除演算及び誤り値計算ユニット」は、誤り位置多項式と誤り評価多項式を計算するものであり、回路で構成されているから、本願発明の「Λ・Ω計算回路」に相当する。
引用例に記載された発明の「誤り位置」は、情報であるから、本願発明の「誤り位置の情報」に相当し、引用例に記載された発明の「誤り位置多項式から誤り位置を求め」ることは、本願発明の「誤り位置多項式情報から誤り位置の情報を計算する」に相当する。
引用例に記載された発明の「誤りの値」は、本願発明の「誤り量の情報」に相当し、引用例に記載された発明の「誤り位置多項式と誤り評価多項式とから誤りの値を計算し」は、本願発明の「誤り位置多項式情報と誤り評価多項式とから誤り量の情報を計算する」に相当する。
引用例に記載された発明の「誤り訂正された多項式」は、情報であるから、本願発明の「訂正情報」に相当し、引用例に記載された発明の「誤り訂正ユニット」は、受信した符号語の修正をおこなっており、回路で動作するから、本願発明の「受信符号語修正回路」に相当する。引用例に記載された発明の「受信多項式と誤り位置と誤りの値とから誤り訂正された多項式を求める誤り訂正ユニット」は、本願発明の「符号化データ情報と誤り位置情報と誤り量情報とから訂正情報を出力する受信符号語修正回路」に相当する。

そうすると、本願発明と引用例に記載された発明とは、
「ガロア体GFを使用するリード・ソロモン復号器において、
符号化データのシンドローム情報を計算するシンドローム計算回路と、
前記シンドローム情報からユークリッド・アルゴリズムによる誤り位置多項式情報及び誤り評価多項式情報を計算するΛ・Ω計算回路と、
前記誤り位置多項式情報から誤り位置の情報を計算し、
前記誤り位置多項式情報と前記誤り評価多項式情報とから誤り量の情報を計算し、
前記符号化データ情報と前記誤り位置情報と前記誤り量情報とから訂正情報を出力する受信符号語修正回路を有するリード・ソロモン復号器」の点で、一致し、以下の点で、相違する。

相違点a.
本願発明では、誤りの位置の情報を計算するのに、「誤り位置計算回路」を用い、誤り量の情報を計算するのに、「誤り量計算回路」を用いているのに対して、引用例に記載された発明では、誤り位置の情報を計算したり、誤り量を計算するとはあるが、回路によって行っているかどうか不明な点。
相違点b.
本願発明では、リード・ソロモン復号器が、「前記シンドローム計算回路により算出された前記シンドローム情報に対して32次多項式割り算を実行して商計算入力分母情報及び/または商計算入力分子情報を生成する誤り評価多項式計算回路と、ユークリッド・アルゴリズムで使用する商の計算を予め格納するとともに、ユークリッド・アルゴリズムにおける割り算を実行する際に当該割り算の実行に代えて当該割り算に応じた商を前記格納された商の中から選択して出力するとともに、前記ユークリッド・アルゴリズムで使用する商の計算を予め格納する際、前記商計算入力分母情報及び前記商計算入力分子情報をアドレスに見立て、当該アドレスに対して予め計算された商のデータを格納する商ROM」を有しているのに対して、引用例には、それいについての記載がない点。

上記相違点について、検討する。
相違点a.について。
誤りの位置の情報を計算したり、誤り量の情報を計算するのに、回路を用いて行うことは、常套手段であるから、引用例に記載された発明において、誤り位置計算回路や誤り量計算回路を用いて、誤りの位置の情報を計算し、誤り量の情報を計算することは、当業者が容易になし得ることと認められる。

相違点b.について。
引用例において、シンドローム多項式から、誤り位置多項式及び誤り評価多項式を計算する時、ユークリッド互除演算を行うが、ユークリッド互除演算は、引用例について摘記した3(2)ロ)に記載されているように、Z2tとシンドローム多項式S(z)の最大公約多項式を求めることで、最大公約数を求めるのに、商、剰余を計算しており、該計算をするには、商計算の分母、分子が必要となるから、引用例に記載された発明において、商計算入力分母情報と商計算入力分子情報を生成し、それを何らかの回路で実現することは、明らかである。さらに、周知例1に示される周知技術である「誤り位置計算回路や誤り大きさ計算回路における多項式除算を行うのに、逆元ROMと乗算手段を用いて行う」こと、周知例2、3に示される周知技術である「多項式を多項式で割る除算の剰余を求めるのに、剰余が記録されたメモリを係数に基づいたアドレスで読み出すことにより、剰余を出力する」ことを考慮すると、引用例に記載された発明において、ユークリッド互除法を用いた除算を行うのに、割り算の実行に替えて、商計算の入力分母情報、入力分子情報をアドレスに見立て、アドレスに対して予め計算された商を、格納したメモリを有し、メモリから選択して、出力することは、当業者が容易になし得ることと認められる。
その際、メモリをROMで構成すること、データの大きさに応じて、多項式割り算を32次ですることは、当業者が適宜なし得ることに過ぎない。
そして、本願発明の作用効果も、引用例に記載された発明、及び、周知例1〜3で示される周知技術から当業者が予測できる範囲のものである。

(4)むすび
以上のとおり、本願発明は、引用例に記載された発明、及び、周知例1〜3で示される周知技術に基いて、当業者が容易に発明をすることができたものであるから、特許法第29条第2項の規定により特許を受けることができない。

よって、結論のとおり審決する。
 
審理終結日 2005-02-15 
結審通知日 2005-02-22 
審決日 2005-03-08 
出願番号 特願平11-4602
審決分類 P 1 8・ 56- Z (H03M)
P 1 8・ 121- Z (H03M)
最終処分 不成立  
前審関与審査官 近藤 聡  
特許庁審判長 武井 袈裟彦
特許庁審判官 望月 章俊
衣鳩 文彦
発明の名称 リード・ソロモン復号器及び誤り訂正方法  
代理人 堀 城之  
代理人 堀 城之  

プライバシーポリシー   セキュリティーポリシー   運営会社概要   サービスに関しての問い合わせ