ヒルベルト曲線による走査アドレス・ジェネレータの開発

利用希尔伯特曲线的扫描地址发生器的研制

基本信息

批准号：
07750437
负责人：
鎌田清一郎
金额：
$ 0.58万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1995
资助国家：
日本
起止时间：
1995 至无数据
项目状态：
已结题

项目摘要

本研究の目的は自己相似性を有する空間充填曲線の一種であるヒルベルト曲線の走査アドレス発生のハードウェア化である。ヒルベルト曲線が自己相似性という興味深い性質をもっているにも拘わらず、その走査アドレス発生に時間がかかるという問題があったが、本研究によりルックアップテーブルを利用した高速計算法のハードウェア化が実現可能となった。本研究ではまず、空間次元数2、3、7におけるハードウェアを試作し、走査時間を計測した。(1)2次元空間では画像サイズが256×256画素、基本クロックが1MHzの場合、すべての画素の走査アドレス発生に要する時間が約0.039秒であることを確認した.ハードウェア規模は2進カウンタとルックアップテーブルに相当する小記憶容量のROMを使用することにより、ICとROMの個数は約15個程度で済み、極めてコンパクトに回路構成できることを確認した。また、ROMの部分が論理回路で簡単に設計できることも確認した。(2)3次元空間では256^3空間画素の場合を設計し、1走査に対して約9.39秒であることを確認した。また、ハードウェア規模はICとROMの個数でみると、2次元の場合より若干増えて約20個程度であることを確認した。(3)7次元空間では256^7空間画素の場合を設計し、1走査に対して計算時間が約4.03×10^<10>秒となり、次元数に対して指数関数的に計算時間が増大することを確認した。次に、本手法では並列計算が可能であるため、その並列ハードウェアを試作し、並列度に対する計算時間を計測した。実験の結果、前記(1)と同じ条件に対して並列度2の場合には約0.019秒となり、約1/2の計算時間になった。また並列度4の場合は約0.012秒となり、若干の計算速度向上が図られた。本研究成果により、これまでのラスタ走査の画像通信に対して、圧縮効率の良いヒルベルト走査による画像通信の構築が可能となった。

本研究的目的是将希尔伯特曲线的扫描地址生成硬件化，希尔伯特曲线是一种具有自相似性的空间填充曲线。虽然希尔伯特曲线具有有趣的自相似性，但存在生成扫描地址需要时间的问题，但这项研究使得使用查找表在硬件中实现高速计算方法成为可能。成为。在这项研究中，我们首先制造了空间维度为 2、3 和 7 的原型硬件，并测量了扫描时间。 (1) 在二维空间中，当图像尺寸为256 x 256像素，基本时钟为1MHz时，我们确认生成所有像素的扫描地址所需的时间约为0.039秒。硬件规模是一个二进制计数器通过使用相当于查找表的小存储容量的ROM，IC和ROM的数量可以减少到15个左右，从而可以构建极其紧凑的电路。我们还确认可以使用逻辑电路轻松设计 ROM 部分。（2）在三维空间中，我们设计了256^3个空间像素的情况，并确认一次扫描大约需要9.39秒。此外，我们确认硬件规模（IC 和 ROM 数量）约为 20 个，略多于二维情况。 (3) 在7维空间中，我们设计了256^7个空间像素的情况，一次扫描的计算时间约为4.03×10^<10>秒，并且计算时间随着维数的增加呈指数增长经证实。接下来，由于使用这种方法可以进行并行计算，因此我们制作了并行硬件原型并测量了相对于并行度的计算时间。实验结果，在与上述(1)相同的条件下，当并行度为2时，计算时间约为0.019秒，约为计算时间的1/2。另外，当并行度为4时，大约需要0.012秒，计算速度略有提升。这项研究的结果使得利用希尔伯特扫描构建图像通信成为可能，它比传统的光栅扫描图像通信具有更好的压缩效率。