計算機等の ディジタルシステムにおいては、順次桁上げ加算器や単純な比較 器等、同一の基本回路を一次元に並べた構造を持つ一次元繰り返し組合せ回路 がしばしば用いられる。その計算時間(回路段数)は入力のビット長に比例する。 このような一次元繰り返し回路は木状構造の回路に変換することにより、計算 時間を入力のビット長の対数に比例するように高速化することができる。集積 回路技術の進歩により、一次元繰り返し回路を木状回路へ変換する試み が盛んになると考えられる。木状回路は、構造がより複雑なため、テスト(故 障検査)は一次元繰り返し回路に比べ難しい。本研究では、一次元繰り返し回 路から変換される木状回路のテストについて考察する。 単一セル機能故障の 仮定の下で、変換された木状回路がC-テスト可能、すなわち、回路の大きさに 関わらず一定のテストパターン数でテストできるための、元の一次元繰り返し 回路を構成する基本回路が実現する関数の十分条件を示す。