図面 (/)

技術 符号化/復号装置

出願人 キヤノン株式会社
発明者 岩村恵市
出願日 2001年9月4日 (19年3ヶ月経過) 出願番号 2001-267903
公開日 2003年3月14日 (17年9ヶ月経過) 公開番号 2003-078420
状態 未査定
技術分野 エラーの検出訂正 符号誤り検出・訂正 エラーの検出、防止 時分割多重化通信方式
主要キーワード IC化 高速化処理 検査記号 選択指示信号 BCH符号 並列化処理 FDDI 情報記号
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2003年3月14日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (16)

課題

u倍の処理速度に対してほぼu倍の回路規模で実現可能な効率的な符号化/復号装置を提供する。

解決手段

それぞれが互いに位相の異なる複数のクロックに同期する複数のレジスタRであって、情報系列の各シンボルを当該複数のレジスタのいずれか1つに順次記憶する複数のレジスタR4〜6と、それぞれが前記複数のレジスタRの異なる1つに対応し、当該対応する1つに記憶された各シンボルを符号化する複数のエンコーダ1〜3と、前記複数のエンコーダ1〜3の各々で生成された符号を順にセレクタS8で選択して、前記情報系列に対応する符号系列を作成する。

概要

背景

従来、図1に示すようなディジタル通信システム(またはディジタル記憶システム)において、送信側で誤り訂正符号符号器301により情報を符号化して送信し、通信路302(または記憶媒体)で発生した誤りを、受信側の復号器303で訂正する技術がよく知られている。これらの符号は、コンパクトディスク等の光ディスクによく用いられ、10Mbps程度の処理速度をもつ符号器や復号器はIC化等によって広く実用化されている。

一方、最近ではFDDI等の光ファイバを用いた高速通信の実用化の研究が盛んに行われ、Gbpsオーダの処理速度が実現できる誤り訂正符号の符号器及び復号器が必要とされている。そのために、T.K.Matsushima"A Design of High-Speed Reed-Solomon Codec LSI,"proc・of the 1993 Symp・on Imformation Theoryand Its Application,W22-2,Oct.1993.(以下、文献1)に示されるようにGbpsオーダの処理速度が実現できる誤り訂正符号の符号器及び復号器の研究・開発が行われている。

図4は、従来の符号器及び復号器での処理を説明するためのタイミングチャートである。図4において、横軸時間軸を示す。

図4の(a)において、C1,C2,…をデータを構成するvビット(vは整数)のシンボルとし、それが順次転送されてくるとした場合、文献1の符号器及び復号器は図3の(a)のようにデータの先頭からn個のシンボルを1符号語として扱い、その1符号語内でデータを並列化し複数のシンボルを同時に処理することによって高速化を実現していた。尚、図4の(a)は、図4の(b)等に比べて高速なデータ転送が行われていることを示している。

しかしながら、2倍の高速化を実現するためには、そのための回路規模としては3倍以上の回路規模が必要であるなどのように、高速化に対しては回路規模の増大の問題があった。よって、文献1の手法は処理の高速化に対して回路規模の面で効率的ではなかった。

次に、図6の(a)には、従来の2次元符号の符号器の一例として、積符号を生成する符号器の構成を示す。図の左から順に、第1符号器、バッファ1、第2符号器と接続されている。

第1符号器は、入力した情報記号に対してその各行に対する行検査記号を生成する。次に、バッファ1では、第1符号器から入力した情報記号と行検査記号を、第2符号器が列方向に入力できるように、格納順序を変換して格納する。そして、第2符号器は、バッファ1内の情報記号と行検査記号を列方向に入力して列検査記号を生成する。

次に、図6の(b)には、従来の2次元の積符号を復号する復号器の構成を示す。図の左から順に、第1復号器、バッファ2、第2復号器と接続されている。ここでは、図6の(a)に示した行方向での符号化処理、列方向での符号化処理の手順に対応して、第1復号器で、入力した積符号の符号語に対して列方向での復号、第2復号器で行方向での復号を行う。

しかしながら、これらの積符号の符号/復号器では、高速な入力データに対する処理ができず、また、バッファ1、バッファ2を要するので、回路構成規模が大きいという問題があった。なお、2次元構成の符号は積符号に限らないが、同様の問題を生じていた。

概要

u倍の処理速度に対してほぼu倍の回路規模で実現可能な効率的な符号化/復号装置を提供する。

それぞれが互いに位相の異なる複数のクロックに同期する複数のレジスタRであって、情報系列の各シンボルを当該複数のレジスタのいずれか1つに順次記憶する複数のレジスタR4〜6と、それぞれが前記複数のレジスタRの異なる1つに対応し、当該対応する1つに記憶された各シンボルを符号化する複数のエンコーダ1〜3と、前記複数のエンコーダ1〜3の各々で生成された符号を順にセレクタS8で選択して、前記情報系列に対応する符号系列を作成する。

目的

本発明は、上記従来例に鑑みてなされたもので、u倍の処理速度に対してほぼu倍の回路規模で実現可能な効率的な符号化/復号装置を提供することを目的とする。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

それぞれが互いに位相の異なる複数のクロックに同期する複数の記憶手段であって、情報系列の各シンボルを当該複数の記憶手段のいずれか1つに順次記憶する複数の記憶手段と、それぞれが前記複数の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルを符号化する複数の符号化手段と、前記複数の符号化手段の各々で生成された符号を順に選択して、前記情報系列に対応する符号系列を作成する符号系列作成手段とを備えることを特徴とする符号化装置

請求項2

前記複数の符号化手段の各々の符号化処理速度は、前記情報系列の転送速度未満であることを特徴とする請求項1に記載の符号化装置。

請求項3

それぞれが互いに位相の異なる複数のクロックに同期する複数の第1の記憶手段であって、情報系列の各シンボルを当該複数の記憶手段のいずれか1つに順次記憶する複数の第1の記憶手段と、それぞれが前記複数の第1の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルを符号化する複数の第1の符号化手段と、前記複数の第1の符号化手段の出力からそれぞれが互いに異なる1つの出力を選択して当該複数の第1の符号化手段の出力と同数の出力を行なう選択手段と、それぞれが互いに位相の異なる複数のクロックに同期して、前記選択手段の異なる1つの出力を記憶する複数の第2の記憶手段と、それぞれが前記複数の第2の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルを符号化する複数の第2の符号化手段と、前記複数の第2の符号化手段の各々で生成された符号を順に選択して、前記情報系列に対応する符号系列を作成する符号系列作成手段とを備えることを特徴とする符号化装置。

請求項4

前記選択手段が、前記第2の符号化手段で符号化されるシンボルの組合せが前記第1の符号化手段で符号化されるシンボルの組合せとは異なる組合せとなるように、前記複数の第1の符号化手段の出力を選択することを特徴とする請求項3に記載の符号化装置。

請求項5

それぞれが互いに位相の異なる複数のクロックに同期する複数の記憶手段であって、符号系列の各シンボルを当該複数の記憶手段のいずれか1つに順次記憶する複数の記憶手段と、それぞれが前記複数の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルを復号する複数の復号手段と、前記複数の復号手段の各々で復号されたシンボルを順に選択して、前記符号系列に対応する情報系列を作成する情報系列作成手段とを備えることを特徴とする復号装置

請求項6

前記複数の復号手段の各々の復号処理速度は、前記符号系列の転送速度未満であることを特徴とする請求項5に記載の復号装置。

請求項7

それぞれが互いに位相の異なる複数のクロックに同期する複数の第1の記憶手段であって、符号系列の各シンボルを当該複数の記憶手段のいずれか1つに順次記憶する複数の第1の記憶手段と、それぞれが前記複数の第1の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルを復号する複数の第1の復号手段と、前記複数の第1の復号手段の出力からそれぞれが互いに異なる1つの出力を選択して当該複数の第1の復号手段の出力と同数の出力を行なう選択手段と、それぞれが互いに位相の異なる複数のクロックに同期して、前記選択手段の異なる1つの出力を記憶する複数の第2の記憶手段と、それぞれが前記複数の第2の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルを復号する複数の第2の復号手段と、前記複数の第2の復号手段の各々で復号されたシンボルを順に選択して、前記符号系列に対応する情報系列を作成する情報系列作成手段とを備えることを特徴とする復号装置。

請求項8

前記複数の第1及び第2の復号手段は、それぞれが対応する1つの記憶手段に記憶された各シンボルからシンドロームを生成する複数のシンドローム生成手段と、前記複数のシンドローム生成手段に対して共通に設けられ、生成された各シンドロームに基づいて誤り位置多項式誤り数値多項式とを導出する多項式導出手段と、前記多項式導出手段で導出された誤り位置多項式と誤り数値多項式とに基づいて誤り位置の検出と誤り数値の導出とを行なう複数の誤り訂正手段とを備えることを特徴とする請求項7に記載の復号装置。

請求項9

それぞれが互いに位相の異なる複数のクロックに同期する複数の第1の記憶手段であって、符号系列の各シンボルを当該複数の記憶手段のいずれか1つに順次記憶する複数の第1の記憶手段と、それぞれが前記複数の第1の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルからシンドロームを生成する複数のシンドローム生成手段と、前記複数のシンドローム生成手段に対して共通に設けられ、生成された各シンドロームに基づいて誤り位置多項式と誤り数値多項式とを導出する多項式導出手段と、前記多項式導出手段で導出された誤り位置多項式と誤り数値多項式とに基づいて誤り位置の検出と誤り数値の導出とを行なう複数の誤り訂正手段と、前記複数の誤り訂正手段の各々で復号されたシンボルを順に選択して、前記符号系列に対応する情報系列を作成する情報系列作成手段とを備えることを特徴とする復号装置。

技術分野

0001

本発明は、ディジタル通信システム及びディジタル記憶システムにおいて通信路または記憶媒体で受けた誤りを、受信側で訂正する誤り訂正符号の符号化/復号装置に関するものである。

背景技術

0002

従来、図1に示すようなディジタル通信システム(またはディジタル記憶システム)において、送信側で誤り訂正符号の符号器301により情報を符号化して送信し、通信路302(または記憶媒体)で発生した誤りを、受信側の復号器303で訂正する技術がよく知られている。これらの符号は、コンパクトディスク等の光ディスクによく用いられ、10Mbps程度の処理速度をもつ符号器や復号器はIC化等によって広く実用化されている。

0003

一方、最近ではFDDI等の光ファイバを用いた高速通信の実用化の研究が盛んに行われ、Gbpsオーダの処理速度が実現できる誤り訂正符号の符号器及び復号器が必要とされている。そのために、T.K.Matsushima"A Design of High-Speed Reed-Solomon Codec LSI,"proc・of the 1993 Symp・on Imformation Theoryand Its Application,W22-2,Oct.1993.(以下、文献1)に示されるようにGbpsオーダの処理速度が実現できる誤り訂正符号の符号器及び復号器の研究・開発が行われている。

0004

図4は、従来の符号器及び復号器での処理を説明するためのタイミングチャートである。図4において、横軸時間軸を示す。

0005

図4の(a)において、C1,C2,…をデータを構成するvビット(vは整数)のシンボルとし、それが順次転送されてくるとした場合、文献1の符号器及び復号器は図3の(a)のようにデータの先頭からn個のシンボルを1符号語として扱い、その1符号語内でデータを並列化し複数のシンボルを同時に処理することによって高速化を実現していた。尚、図4の(a)は、図4の(b)等に比べて高速なデータ転送が行われていることを示している。

0006

しかしながら、2倍の高速化を実現するためには、そのための回路規模としては3倍以上の回路規模が必要であるなどのように、高速化に対しては回路規模の増大の問題があった。よって、文献1の手法は処理の高速化に対して回路規模の面で効率的ではなかった。

0007

次に、図6の(a)には、従来の2次元符号の符号器の一例として、積符号を生成する符号器の構成を示す。図の左から順に、第1符号器、バッファ1、第2符号器と接続されている。

0008

第1符号器は、入力した情報記号に対してその各行に対する行検査記号を生成する。次に、バッファ1では、第1符号器から入力した情報記号と行検査記号を、第2符号器が列方向に入力できるように、格納順序を変換して格納する。そして、第2符号器は、バッファ1内の情報記号と行検査記号を列方向に入力して列検査記号を生成する。

0009

次に、図6の(b)には、従来の2次元の積符号を復号する復号器の構成を示す。図の左から順に、第1復号器、バッファ2、第2復号器と接続されている。ここでは、図6の(a)に示した行方向での符号化処理、列方向での符号化処理の手順に対応して、第1復号器で、入力した積符号の符号語に対して列方向での復号、第2復号器で行方向での復号を行う。

0010

しかしながら、これらの積符号の符号/復号器では、高速な入力データに対する処理ができず、また、バッファ1、バッファ2を要するので、回路構成規模が大きいという問題があった。なお、2次元構成の符号は積符号に限らないが、同様の問題を生じていた。

発明が解決しようとする課題

0011

本発明は、上記従来例に鑑みてなされたもので、u倍の処理速度に対してほぼu倍の回路規模で実現可能な効率的な符号化/復号装置を提供することを目的とする。

課題を解決するための手段

0012

上述した目的を達成するため、本発明の符号化装置は、それぞれが互いに位相の異なる複数のクロックに同期する複数の記憶手段であって、情報系列の各シンボルを当該複数の記憶手段のいずれか1つに順次記憶する複数の記憶手段と、それぞれが前記複数の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルを符号化する複数の符号化手段と、前記複数の符号化手段の各々で生成された符号を順に選択して、前記情報系列に対応する符号系列を作成する符号系列作成手段とを備える。

0013

また、本発明の他の態様によれば、符号化装置に、それぞれが互いに位相の異なる複数のクロックに同期する複数の第1の記憶手段であって、情報系列の各シンボルを当該複数の記憶手段のいずれか1つに順次記憶する複数の第1の記憶手段と、それぞれが前記複数の第1の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルを符号化する複数の第1の符号化手段と、前記複数の第1の符号化手段の出力からそれぞれが互いに異なる1つの出力を選択して当該複数の第1の符号化手段の出力と同数の出力を行なう選択手段と、それぞれが互いに位相の異なる複数のクロックに同期して、前記選択手段の異なる1つの出力を記憶する複数の第2の記憶手段と、それぞれが前記複数の第2の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルを符号化する複数の第2の符号化手段と、前記複数の第2の符号化手段の各々で生成された符号を順に選択して、前記情報系列に対応する符号系列を作成する符号系列作成手段とを備える。

0014

また、本発明の他の態様によれば、復号装置に、それぞれが互いに位相の異なる複数のクロックに同期する複数の記憶手段であって、符号系列の各シンボルを当該複数の記憶手段のいずれか1つに順次記憶する複数の記憶手段と、それぞれが前記複数の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルを復号する複数の復号手段と、前記複数の復号手段の各々で復号されたシンボルを順に選択して、前記符号系列に対応する情報系列を作成する情報系列作成手段とを備える。

0015

また、本発明の他の態様によれば、復号装置に、それぞれが互いに位相の異なる複数のクロックに同期する複数の第1の記憶手段であって、符号系列の各シンボルを当該複数の記憶手段のいずれか1つに順次記憶する複数の第1の記憶手段と、それぞれが前記複数の第1の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルを復号する複数の第1の復号手段と、前記複数の第1の復号手段の出力からそれぞれが互いに異なる1つの出力を選択して当該複数の第1の復号手段の出力と同数の出力を行なう選択手段と、それぞれが互いに位相の異なる複数のクロックに同期して、前記選択手段の異なる1つの出力を記憶する複数の第2の記憶手段と、それぞれが前記複数の第2の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルを復号する複数の第2の復号手段と、前記複数の第2の復号手段の各々で復号されたシンボルを順に選択して、前記符号系列に対応する情報系列を作成する情報系列作成手段とを備える。

0016

また、本発明の他の態様によれば、復号装置に、それぞれが互いに位相の異なる複数のクロックに同期する複数の第1の記憶手段であって、符号系列の各シンボルを当該複数の記憶手段のいずれか1つに順次記憶する複数の第1の記憶手段と、それぞれが前記複数の第1の記憶手段の異なる1つに対応し、当該対応する1つに記憶された各シンボルからシンドロームを生成する複数のシンドローム生成手段と、前記複数のシンドローム生成手段に対して共通に設けられ、生成された各シンドロームに基づいて誤り位置多項式誤り数値多項式とを導出する多項式導出手段と、前記多項式導出手段で導出された誤り位置多項式と誤り数値多項式とに基づいて誤り位置の検出と誤り数値の導出とを行なう複数の誤り訂正手段と、前記複数の誤り訂正手段の各々で復号されたシンボルを順に選択して、前記符号系列に対応する情報系列を作成する情報系列作成手段とを備える。

発明を実施するための最良の形態

0017

本発明に係る実施形態のポイントの一つは、図4の(a)のような高速なデータを位相の異なるクロックで制御された複数のレジスタで受け、図4の(b)〜(d)のような複数の低速なデータに分割することによって、それに応じた数の低速な符号器及び復号器を用いて誤り訂正の符号化及び復号処理を行い、それら低速な処理回路からの出力を再び合成することによって、全体として高速処理を実現することにある。

0018

[実施形態1]実施形態1の符号器の構成を図2に示す。

0019

図2の3つのエンコーダ(encoder)(1、2、3)は低速なデータを処理できる公知の符号器とする。例えば、エンコーダ(1、2、3)は、図4の(a)のような高速なデータの1/3程度の処理速度であれば処理可能な誤り訂正符号器であるとする。

0020

以後、図2図4図5で( )内に記述されているアルファベットは、信号の種類を示すが、同じアルファベットのものは、同じ信号であることを表すものとする。

0021

そこで、図4の(a)のような高速データ図2の(a)に入力されるとしたとき、それをCK1,CK2,CK3の位相の異なる3種類のクロックによって制御される3つのレジスタR(4、5、6)に入力する。これによって、図4の(b),(c),(d)のようにそれぞれ位相が異なる図4の(a)の1/3の低速データに3分割される。

0022

図2の3つのエンコーダ(encoder)(1、2、3)は、図4の(a)の1/3の速度で処理可能としたので、各入力データ誤り訂正符号化されて、図2の(e),(f),(g)に各々出力される。この処理のタイミングチャートを図5に表す。

0023

これらの信号(e),(f),(g)を、図2の制御(control)信号(7)で制御されるセレクタS(8)で選択して(h)に出力する。この制御(control)信号(7)に基づいて、セレクタS(8)は、図5のように各入力を選択する。これを、クロックCK(9)に同期させたレジスタR(10)を用いて、(i)に出力することによって、図4の(a)のような高速データに対応した処理が可能になる。

0024

これは、図3の(b)のようにデータをシンボルの並び順と異なる3つの符号語に分割し、各々の符号語をそれぞれ異なるエンコーダ(encoder)で符号化処理することを意味する。この場合、符号語としてまとめられるシンボルの並びはバラバラであるが(図3の(a)の並び順が正しいとした場合)、誤り訂正符号化は、例えば図1の通信路302の誤りに対して行われる場合、符号器301への入力シンボルの並び順と復号器303からの出力シンボルの並び順が一致していれば、途中のシンボルのまとまりは任意である。よって、本実施形態では、シンボルの並び順を変えることによって、容易に並列化を実現し高速符号化を可能にした。ただし、図3の(b)での形態の処理では、図3の(a)より3倍のデータが必要である。

0025

このような従来の3倍の処理速度を持つ高速符号器を構成するためには、公知のエンコーダ(encoder))3つの他に、4つのレジスタR(4、5、6、10)と、セレクタS(8)を加えるだけでよい。これらのレジスタおよびセレクタは、エンコーダ(encoder)3つの回路規模に比べて十分小さいので、図2の符号器は、従来のエンコーダ(encoder)の3倍の処理速度を得るために、ほぼ3倍の回路規模で容易に構成できる。

0026

本実施形態では、説明を具体化するために、従来のエンコーダ(encoder)の3倍の処理速度をもつ符号器の構成方法を説明したが、一般に、u倍の処理速度を実現するにはエンコーダ(encoder)の数をu個、レジスタの数をu+1個、入力数uのセレクタ1個の構成で、同様にほぼu倍の回路規模で容易に対応できることが明らかである。

0027

[実施形態2]実施形態2では、図6の(a)に示した従来例とは異なり、シンボルの並び順を変えるために図3の(a)のデータを一時格納するバッファを必要とせずに、容易に実現できる符号器を提供する。

0028

本実施形態の符号器の構成を図7に示す。

0029

図7を参照して、3つのエンコーダ(1、2、3)、3つのレジスタR(4、5、6)までの構成は、図2の符号器と同じであり、図7の(a)〜(g)の入出力は、図2での動作と同様である。

0030

それ以降の動作を図8を用いて説明する。ここで、図7図8の( )内のアルファベットが同じものは同じ信号を示す。図7のセレクタS(18)は、図2のセレクタS(8)と異なり、制御信号(control)(20)によって制御されて、3つの信号を出力する。即ち、
(j)の信号: 所定のタイミングで(e)→(f)→(g)→(e)→…の順で選択した結果を出力する。

0031

(k)の信号: (f)→(g)→(e)→(f)→…の順で選択した結果を出力する。

0032

(l)の信号: (g)→(e)→(f)→(g)→…の順で選択した結果を出力する。

0033

これらをクロックCK4に同期してそれぞれラッチすることによって、図7のセレクタS(18)の出力(j),(k),(l)を受けるレジスタ(30、31、32)は、各々(m),(n),(o)のような信号を出力する。これらの信号は、エンコーダ(33、34、35)で処理できる処理速度であるので、それらの信号を受けて各々符号化を行い、(p),(q),(r)に符号化信号を出力する。

0034

次に、それ以降の動作を図9を用いて説明する。その出力された信号は、図9(p),(q),(r)のようになる。そして、セレクタS(36)では、制御信号(38)の選択指示に従い、(p),(q),(r)から1つの信号を選択する。制御信号(38)は、図9に示すように、(p),(q),(r),(r),(p),(q),(q),(r),(p)…の順に選択させる選択指示信号である。そして、図9の(s)に示すような符号化された信号シリアル系列が、セレクタS(36)から出力される。

0035

次に、この信号シリアル系列は、クロック(39)で同期させてレジスタRから(t)として出力することによって、元のシンボルの並び順に戻すことができる。

0036

これは図3の(b)のデータを最初の符号化では第1の実施形態と同様に横方向に行い、次の符号化ではシンボルの並び順の異なる斜め下方向に行うことを意味する。しかし、図6の(a)の従来例のようにシンボルの並び順を変えるために図3の(a)のデータを一時格納するバッファを必要としない符号器を容易に実現できる。

0037

本実施形態では、前実施形態と同様に理解を容易にするために、従来のエンコーダの3倍の処理速度をもつ符号器の構成法を説明したが、u倍の処理速度に対しても同様に容易に対応できることは明らかである。

0038

[実施形態3]以上説明した実施形態は符号化装置について説明したが、実施形態3では、その符号化装置で生成された符号語を入力して高速に復号する復号器を提供する。

0039

図10に実施形態3の復号器の基本構成を示す。ここで、3つのデコーダ(decoder)(54、55、56)は低速なデータを処理できる公知の復号器でよく、例えば図4の(a)のような高速なデータの1/3程度の処理速度のデータを処理できる誤り訂正復号器であるとする。

0040

以後、図10を参照して、実施形態3の復号器の詳細説明を行うが、図10中( )で示されている信号の動作タイミングは、図4図5で示した( )で示されている信号の動作タイミングと同様である。しかし、実施形態2までとは、信号内容は異なることに注意されたい。例えば、実施形態2までの(a)信号は符号化される前のデータを意味していたが、本実施形態では、受信された符号化データを意味する。

0041

図4の(a)のようなタイミングの高速符号化データが図10の(a)に入力されたとき、それをCK1(60),CK2(61),CK3(62)の位相の異なる3種類のクロックに同期して、それぞれ制御されるレジスタR(54、55、56)にラッチする。

0042

この処理によって、図4の(b),(c),(d)の各タイミングチャートに示したように、図4の(a)の1/3の低速データに3分割される。図10の3つのデコーダ(decoder)(54、55、56)は、図4の(a)の1/3の速度のデータでは処理可能としたので、各入力データを誤り訂正復号して図10の(e),(f),(g)に各々出力される。このタイミングを図5に示す。これらの信号を図10の制御(control)(50)信号で制御されるセレクタS(53)で選択して(h)に出力する。この制御(control)(50)信号は、図5のように各入力を選択する要求信号である。次に、セレクタS(53)で選択された信号(h)を、クロックCK(51)に同期してレジスタR(52)にラッチして、信号(i)として出力する。この処理によって、図4の(a)のような高速データに対応した復号化処理が可能になる。

0043

これは、図3の(b)のように符号語をシンボルの並び順と異なる3つの符号語に分割して、各々の符号語をそれぞれ異なるデコーダ(decoder)で復号することを意味する。この場合、符号語としてまとめられているシンボルの並びはバラバラであるが(図3の(a)の並びが正しいとした場合)、誤り訂正符号化は例えば図1の通信路302の誤りに対して行われる場合、符号器301への入力シンボルの並び順と復号器303からの出力シンボルの並び順が一致していれば途中のシンボルのまとまりは任意である。よって、本実施形態ではシンボルの並び順を変えることによって、容易に並列化を実現して高速復号化を可能にしたものである。

0044

また、本実施形態の高速復号器を構成するためには、公知の3つのデコーダ(decoder)(54、55、56)の他に、4つのレジスタR(57、58、59、52)と、1つのセレクタS(52)を加えるだけでよい。これらのレジスタおよびセレクタはデコーダ(decoder)(54、55、56)の回路規模に比べて十分小さいので、図10の復号器は従来のデコーダの3倍の処理速度を得るために、ほぼ3倍の回路規模で容易に構成できる。

0045

本実施形態では、理解を容易にするために、従来のデコーダの3倍の処理速度をもつ復号器の構成法を説明したが、一般に、u倍の処理速度を実現するには従来のデコーダの数をu個、レジスタの数をu+1個、入力数uのセレクタ1個にすれば、同様にほぼu倍の回路規模で容易に対応できることは明らかである。

0046

[実施形態4]実施形態4では、図6の(b)に示した従来例とは異なりシンボルの並び順を変えるために図3の(a)の並びの符号語を一時格納するバッファを必要とせずに、容易に復号処理を実現できる復号器を提供する。

0047

図11に、第4の実施形態の復号器の構成を示す。

0048

図11を参照して、3つのデコーダ(54、55、56)、3つのレジスタR(57、58、59)までの構成は、図10の復号器と同じである。また、図11の(a)〜(g)は、図10で説明した各信号と同様である。

0049

それ以降の動作を図8に示したタイミングチャートを用いて説明する。ここで、図11図8の( )内のアルファベットが同じものは同じ信号を示す。図11のセレクタS(70)は、図10のセレクタS(53)と異なり、制御信号(control)(80)によって制御されて、3つの信号を出力する。即ち、
(j)の信号: 所定のタイミングで(e)→(f)→(g)→(e)→…の順で選択した結果を出力する。

0050

(k)の信号: (f)→(g)→(e)→(f)→…の順で選択した結果を出力する。

0051

(l)の信号: (g)→(e)→(f)→(g)→…の順で選択した結果を出力する。

0052

これをクロックCK4(84)に同期してラッチすることによって、図11のセレクタS(70)の出力を受けるレジスタ(71、72、73)は、各々(m),(n),(o)の信号を出力する。これらの信号は、デコーダ(74、75、76)で処理できる処理速度であるので、それらの信号を受けて各々復号化を行い、(p),(q),(r)に復号化信号を出力する。

0053

次に、それ以降の動作を図9を用いて説明する。その出力された信号は、図9(p),(q),(r)のようになる。そして、セレクタS(77)では、制御信号(79)の選択指示に従い、(p),(q),(r)から1つの信号を選択する。制御信号(79)は、図9に示すように、(p),(q),(r),(r),(p),(q),(q),(r),(p)…の順に選択させる選択指示信号である。そして、図9の(s)に示すようなタイミングの復号化された信号シリアル系列が、セレクタS(77)から出力される。

0054

次に、この信号シリアル系列は、クロック(85)で同期化させて、レジスタRから出力することによって、元のシンボルの並び順に戻すことができる。

0055

これは図3の(b)に示した並びの符号語に対する最初の復号化では第3の実施形態と同様に横方向に行い、次の復号化ではシンボルの並び順の異なる斜め下方向に行うことを意味する。しかし、図6の(b)の従来例のようにシンボルの並び順を変えるために、図3の(a)のデータを一時格納するバッファを必要としない復号器を容易に実現できる。

0056

本実施形態では、前実施形態と同様に理解を容易にするために、従来のデコーダの3倍の処理速度をもつ復号器の構成法を説明したが、u倍の処理速度に対しても同様に容易に対応できることは明らかである。

0057

[実施形態5]BCH符号(Bose-Chaudhuri-Hocquenghem code)やリードソロモン符号RS符号)などでの復号処理は、例えば、「“VLSI向きリードソロモン符号化復号方式;岩,今井,土肥:”,信学論(A),Vol.J71−A,No.3,pp.751−759,1988.3.(以後、“文献2”と呼ぶ)」に示されるようないくつかの処理から構成される。その復号処理のなかで、シンドローム生成処理(以下、“syndrome処理”と呼ぶ)と誤り位置及び誤り数値の導出を含む誤り訂正処理(以後、“Chien処理”)の処理時間は符号長nに依存し、誤り位置多項式と誤り数値多項式を導出する多項式導出処理は符号の訂正能力を決める最小距離dに依存することが文献2に示されている。

0058

通常、n>>dであるので、syndrome処理とChien処理は高速処理が要求されるが、それ以外の処理(多項式導出処理)は高速処理が要求されない場合もある。このような場合、復号器全体を並列化して高速処理に対応させる必要はなく高速処理が要求される部分だけを並列化することによって、全体の回路規模の増加を押さえることができる。

0059

本実施形態では、上述したように高速化を要求される部分だけを並列化した復号器の構成を図12に示す。

0060

図12において、3つのsyndrome(100、101、102)と3つのChien(104、105、106)は、それぞれ公知のシンドローム(syndrome)処理とチェン(Chien)処理を行うブロックである。例えば、図4の(a)に示したタイミングチャートに示すような高速なデータを処理する1/3程度の処理速度を有する回路であるとする。以後、図12図4図5の( )内のアルファベットは同じ信号を表す。

0061

図4の(a)に示すようなタイミングを有する高速データが図12の(a)から入力されるとしたとき、それをCK1(114),CK2(115),CK3(116)で表される位相の異なる3種類のクロックによってそれぞれ制御されるレジスタR(109、110、111)に入力される。これによって、図4(b),(c),(d)のように、図4の(a)の1/3の低速データに3分割される。

0062

図12のsyndrome(100、101、102)は、図4の(a)の1/3の速度は処理可能としたので、各符号語に対するシンドロームが図12のsyndrome(100、101、102)から各々出力される。これらをより低速な処理でよいシンドローム処理とチェン処理以外の処理を行う公知の処理回路P(103)に入力し、その結果をそれぞれChien部(104、105、106)に入力する。各Chien部(104、105、106)では、誤り位置と誤り数値の導出を含む誤り訂正処理を(b),(c),(d)と同等の速度で行い各々(e),(f),(g)から出力する。

0063

これらの信号を図12の制御信号(113)で制御されるセレクタS(107)で選択して(h)に出力する。この出力は図5に示すタイミングチャートのようになり、これをレジスタR(108)でクロックCK(117)に同期させて(i)として出力することによって、図4の(a)に示したタイミングの高速データにも対応できる。

0064

以上のように、復号処理をいくつかに分解できる場合、高速化が要求されない部分は共通化した回路を構成することによって、全体の回路規模を抑えた復号器が実現できる。以後、このように共通化できる部分を1つにした復号器をマルチデコーダ(Multi-decoder)と呼ぶことにする。図12では点線で囲んだ部分がそれに当たる。ここでは、図3の(b)に示すようにデータがシンボルの並び順と異なる3つの符号語に分割される。

0065

以上説明したように、図12の復号器によって、従来のデコーダの処理速度の3倍の処理を3倍以下の回路規模で容易に実現できる。

0066

本実施形態では理解を容易にするために、従来の3倍の処理速度をもつ復号器の構成法を説明したが、u倍の処理速度に対してはsyndrome部やChien部の数をu個、レジスタの数をu+1個、セレクタの入力数をuにすれば、同様に容易に対応できることは明らかである。

0067

また、u倍の高速化に対して回路P(103)での処理速度が追いつかない場合は、本実施形態でのsyndrome部やChien部を複数持つアイデアを回路Pにも適用して、回路Pを複数もつ構成にすることにより、同様に高速処理を実現できることは言うまでもない。

0068

[実施形態6]実施形態6では、図6の(b)に示した従来例のようにシンボルの並び順を変えるための図3の(a)の並びの符号語を一時格納するバッファを必要とせずに、実施形態5で説明したsyndrome処理と誤り位置及び誤り数値の導出を含む誤り訂正処理を含む復号処理を容易に実現した復号器を提供する。

0069

図13に、実施形態6の復号器の構成を示す。

0070

図13において、マルチデコーダ(150)は実施形態5で説明したマルチデコーダ(図12)と同じ構成を持つ。マルチデコーダ(150)より左の回路構成もまた、図12と同じである。

0071

また、図13の(a)〜(g)は、図12で説明した各信号と同様である。

0072

次に、マルチデコーダ(150)以降の動作を、図8に示したタイミングチャートを用いて説明する。ここで、図13図8の( )内のアルファベットが同じものは同じ信号を示す。図13のセレクタS(151)は、図12のセレクタS(107)と異なり、制御信号(control)(159)によって制御されて、3つの信号を出力する。即ち、
(j)の信号: 所定のタイミングで(e)→(f)→(g)→(e)→…の順で選択した結果を出力する。

0073

(k)の信号: (f)→(g)→(e)→(f)→…の順で選択した結果を出力する。

0074

(l)の信号: (g)→(e)→(f)→(g)→…の順で選択した結果を出力する。

0075

これをクロックCK4(160)に同期してラッチすることによって、図13のセレクタS(151)の出力を受けるレジスタ(152、153、154)は、各々(m),(n),(o)の信号を出力する。これらの信号は、マルチデコーダ(155)で処理できる処理速度であるので、それらの信号を受けて各々復号化を行い、(p),(q),(r)に復号化された信号を出力する。

0076

次に、それ以降の動作を図9を用いて説明する。その出力された信号は、図9の(p),(q),(r)のようになる。そして、セレクタS(156)では、制御信号(158)の選択指示に従い、(p),(q),(r)から1つの信号を選択する。制御信号(158)は、図9に示すように、(p),(q),(r),(r),(p),(q),(q),(r),(p)…の順に選択させる選択指示信号である。そして、図9の(s)に示すようなタイミングの復号化された信号シリアル系列が、セレクタS(156)から出力される。

0077

次に、この信号シリアル系列は、クロック(161)で同期化させて、レジスタR(157)から出力することによって、元のシンボルの並び順に戻すことができる。

0078

これは、図3の(b)に示した並びの符号語に対する最初の復号化では第5の実施形態と同様に横方向に行い、次の復号化ではシンボルの並び順の異なる斜め下方向に行うことを意味する。しかし、図6の(b)の従来例のようにシンボルの並び順を変えるために、図3の(a)のデータを一時格納するバッファを必要としない復号器を容易に実現できる。

0079

本実施形態では、前実施形態と同様に理解を容易にするために、従来のデコーダの3倍の処理速度をもつ復号器の構成法を説明したが、u倍の処理速度に対しても同様に容易に対応できることは明らかである。

0080

[実施形態7]符号器と復号器を含む装置は符号・復号器(codec)と呼ばれ、それに対する実施形態を図14に示す。図14のcodecは低速なデータを処理できる公知の符号化・復号器とし、例えば、図4の(a)に示したような高速なデータを処理する処理速度の1/3程度の処理能力のある誤り訂正符号・復号器であるとする。以後、図14図4図5の( )内のアルファベットは同じ信号を表す。

0081

図4の(a)のような高速データが図14の(a)から入力されるとしたとき、それをCK1(209),CK2(210),CK3(211)で表される位相の異なる3種類のクロックによって制御されるレジスタR(203、204、205)に入力する。これによって、図4の(b),(c),d)のように図4の(a)の1/3の低速データに3分割される。

0082

図14のcodecは図4の(a)の1/3の速度では処理可能としたので、各入力データは符号化または復号化されて、図14の(e),(f),(g)から各々出力される。この様子を図5のタイミングチャートに示す。これらの信号を図14の制御信号(control)(208)で制御されるセレクタS(206)で選択して(h)に出力する。この制御信号(208)は図5に示したように各入力を選択する。そして、選択された信号をレジスタR(207)でクロックCK(212)に同期させて(i)から出力することによって、図4の(a)に示した高速データに対応した処理が可能になる。

0083

以上の処理によって、図3の(b)に示したようにデータがシンボルの並び順と異なる3つの符号語に分割され、各々の符号語がそれぞれ異なるcodecで符号・復号化されたことを意味する。この場合、符号語としてまとめられるシンボルの並びはバラバラであるが(図3の(a)の並び順が正しいとした場合)、誤り訂正符号化は、例えば図1に示したような通信路302の誤りに対して行われる場合、符号器301への入力シンボルの並び順と復号器303からの出力シンボルの並び順が一致していれば、途中のシンボルのまとまりは任意である。この性質に鑑み、本実施形態ではシンボルの並び順を変えることによって、容易に並列化処理を実現することにより高速で、かつ回路規模の小さい態様での符号化/復号化処理を可能にした。

0084

また、この高速符号・復号器を構成するためには、公知の3つのcodec他に、4つレジスタRと、1つのセレクタSを加えるだけでよい。これらの追加回路は、3つのcodecの回路規模に比べて十分小さいので、図14の符号・復号器は従来のcodecの3倍の処理速度を得るために、ほぼ3倍の回路規模で容易に構成できる。

0085

本実施形態では、説明を具体化するために従来のcodecの3倍の処理速度をもつ符号・復号器の構成法を説明したが、u倍の処理速度を実現するにはcodecの数をu個、レジスタの数をu+1個、セレクタの入力数をuにすれば、同様に容易に対応できることは明らかである。

0086

また、消失訂正を行う復号器は符号器としても用いられることが知られているので、第3及び第5の実施形態で示したデコーダ(decoder)及びマルチデコーダ(Multi-decoder)が消失訂正を行う場合は、codecの代わりとできることも明らかである。その場合、図10図12の回路は高速データに対する符号・復号器としても用いることができる。

0087

[実施形態8]実施形態8では、図6の(a),(b)に示した従来例のようにシンボルの並び順を変えるための図3の(a)の並びのシンボルを一時格納するバッファを必要とせずに、実施形態7で説明した高速符号・復号化処理を容易に実現したcodecを提供する。

0088

図15に、実施形態8のcodecの構成を示す。

0089

図15において、図15のcodecは実施形態7で説明したcodec(200、201、202)と同じ構成を持つ。また、図15のcodec(200、201、202)と、それらから左に位置する回路構成は図14と同じである。

0090

また、図15の(a)〜(g)は、図14で説明した各信号と同様である。

0091

次に、codec(200、201、202)以降の動作を、図8に示したタイミングチャートを用いて説明する。ここで、図15図8の( )内のアルファベットが同じものは同じ信号を示す。図15のセレクタS(212)は、図14のセレクタS(206)と異なり、制御信号(control)(216)によって制御されて、3つの信号を出力する。即ち、
(j)の信号: 所定のタイミングで(e)→(f)→(g)→(e)→…の順で選択した結果を出力する。

0092

(k)の信号: (f)→(g)→(e)→(f)→…の順で選択した結果を出力する。

0093

(l)の信号: (g)→(e)→(f)→(g)→…の順で選択した結果を出力する。

0094

これをクロックCK4(213)に同期してラッチすることによって、図15のセレクタS(214)の出力を受けるレジスタ(217、218、219)は、各々(m),(n),(o)の信号を出力する。これらの信号は、codecで処理できる処理速度であるので、それらの信号を受けて各々復号化を行い、(p),(q),(r)にcodec処理された信号を出力する。

0095

次に、それ以降の動作を図9を用いて説明する。その出力された信号は、図9の(p),(q),(r)のようになる。そして、セレクタS(223)では、制御信号(215)の選択指示に従い、(p),(q),(r)から1つの信号を選択する。制御信号(215)は、図9に示すように、(p),(q),(r),(r),(p),(q),(q),(r),(p)…の順に選択させる選択指示信号である。そして、図9の(s)に示すようなタイミングのcodec処理された信号シリアル系列が、セレクタS(223)から出力される。

0096

次に、この信号シリアル系列は、クロック(213)で同期化させて、レジスタR(224)から出力することによって、元のシンボルの並び順に戻すことができる。

0097

これは、図3の(b)に示した並びのシンボルに対する最初のcodec処理では第5の実施形態と同様に横方向に行い、次のcodec処理ではシンボルの並び順の異なる斜め下方向に行うことを意味する。しかし、図6の(b)の従来例のようにシンボルの並び順を変えるために、図3の(a)のシンボルを一時格納するバッファを必要としない復号器を容易に実現できる。

0098

本実施形態では、前実施形態と同様に理解を容易にするために、従来のcodecの3倍の処理速度をもつcodecの構成法を説明したが、u倍の処理速度に対しても同様に容易に対応できることは明らかである。

0099

以上説明したように、処理を並列化することによってu倍の回路規模でu倍の高速化を実現する符号器、復号器、codecが容易に構成できることがわかる。

0100

更に、それらの処理が高速化が要求される処理とあまり高速化が要求されない処理に分解できるとき、高速処理を要求される処理だけを並列化することによって、u倍以下の回路規模でu倍の高速化処理が実現できる。

0101

さらに、符号器と復号器を含む装置化または復号器が消失訂正によって符号化処理も実現できる場合は、同様の手法によってu倍またはu倍以下の回路規模でu倍の高速化が実現できる符号化・復号器も実現できる。

0102

さらに、積符号やインターリーブ符号などの処理で従来必要であったシンボルの並び替え用のバッファを不要とした回路規模効率がよくかつ高速に処理できる符号器、復号器、codecを効率的に実現できる。

0103

本実施形態の符号器、復号器、codecは、従来の符号器または復号器に数個のレジスタとセレクタを加えるだけでよいので容易に構成できる。

0104

本実施形態の構成によって、従来のエンコーダやデコーダやcodecでは動作困難であったクロック以上の高速な転送データに対しても誤り訂正符号の符号化、復号化及び符号・復号化が効率的に行える。

発明の効果

0105

以上説明したように本発明によれば、u倍の処理速度に対してほぼu倍の回路規模で実現可能な効率的な符号化/復号装置を提供できる。

図面の簡単な説明

0106

図1誤り訂正符号が必要なシステムの基本的概念図である。
図2本発明に係る実施形態1による符号器の構成図である。
図3シンボルデータの並びを説明する図である。
図4本発明に係る各実施形態を説明するタイミングチャートである。
図5本発明に係る各実施形態を説明するタイミングチャートである。
図6従来の2次元積符号を処理する符号器及び復号器の構成図である。
図7本発明に係る実施形態2の符号器の構成図である。
図8本発明に係る各実施形態を説明するタイミングチャートである。
図9本発明に係る各実施形態を説明するタイミングチャートである。
図10本発明に係る実施形態3の復号器の構成図である。
図11本発明に係る実施形態4の復号器の構成図である。
図12本発明に係る実施形態5のマルチデコーダ(多重符号器)の構成図である。
図13本発明に係る実施形態6のマルチデコーダ(多重符号器)を含むシンボル並べ替え用バッファが不要な符号器の構成図である。
図14本発明に係る実施形態7のcodecの構成図である。
図15本発明に係る実施形態8のシンボル並べ替え用バッファが不要なcodecの構成図である。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ