JPH0713653B2

JPH0713653B2 - 故障検出回路

Info

Publication number: JPH0713653B2
Application number: JP59233153A
Authority: JP
Inventors: 一彦岩崎; 昇山口
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1984-11-07
Filing date: 1984-11-07
Publication date: 1995-02-15
Anticipated expiration: 2010-02-15
Also published as: JPS61112974A

Description

【発明の詳細な説明】〔発明の利用分野〕本発明は理論回路の故障診断方式に係り、特にLSI（Lar
ge Scale Integrated circut）に好適な故障診断方式に
関する。

〔発明の背景〕

論理LSIの自己テストでは、第１図で示すような論理回
路の検査モデルティー．ダブリュー．ウィリアムズ，ケ
イ．ピー．パーカー著“デザイン・フォア・テスタビリ
ィティーア・サーベイ",アイ・イー・イー・イー，トラ
ンスアクションズ・オン・コンピュータズ，第C-31巻，
第１号,1982年１月刊（T.W.Williams,K.P.Parker“Desi
grfor Testahility−A Survey",IEEE Trans.on Compute
rs,Vol.C-31,No.1,Jan,'82）を扱う。被検査回路１はｍ
個の出力系列a₀（ｘ），a₁（ｘ），……a_m-1（ｘ）を情
報圧縮回路２へ出力する。多項式a₁（ｘ）（０ｉｍ
−１）はビツト系列a_i0,a_i1，……，a_in-1の多項式表現
であり、である。情報圧縮回路２へはa_in-1,a_in-2，……，a_i0の
順序で入力されるものとする。

情報圧縮回路２はa₀（ｘ），a₁（ｘ），……，a
_m-1（ｘ）をｍビツトに圧縮し、その結果をシグナチヤS
IG′（ｘ）として故障判定回路３へ出力する。情報の圧
縮は、従来はMISR（Multiple Input Signature Registe
r）と呼ばれる線形フイードバツクシフトレジスタ（FS
R:Feed Back Shift Registera）によつておこなわれて
いた。

故障判定回路３では、被検査回路に故障がない場合のシ
グナチヤSIG（ｘ）とSIG′（ｘ）を比較し、SIG′
（ｘ）＝SIG（ｘ）のときそれぞれ、入力a₁（ｘ），a₂
（ｘ），a₃（ｘ），……，a_m-2（ｘ），a_m-1（ｘ）と前
段のレジスタの内容と係数器15,16,17,……,18,19の排
他的論理和をとり次段のレジスタへ伝える。

ｍ個の入力検査系列a₀（ｘ），a₁（ｘ），……，a
_m-1（ｘ）のうちa₁（ｘ）だけが非零系列（少なくとも
１個の１を含む）であると仮定する。このとき、a
_i（ｘ）以外はオール０であるから第３図で示されるよ
うなFSR、となる。排他的論理和ゲート33は、入力a
_i（ｘ）を前段のレジスタと係数器31の排他的論理和を
とり、レジスタ30へ伝える。排他的論理和ゲート21,22,
23,……,34,……,25はそれぞれ前段のレジスタと、係数
器15,16,17,32,19との排他的論理和をとり次段へ伝え
る。これは除算回路としてよく知られた回路であり、除
多項式Ｇ（ｘ）は、Ｇ（ｘ）＝g_mx^m+g_m-1x^m-1＋…＋g₁x＋g₀ …（２） g_m＝1,g₀＝１と表される。a_i（ｘ）はｉ段目のレジスタへ入力される
ため、被除多項式は xⁱa_i（ｘ）と表わされる。

入力検査パターンa₀（ｘ），a₁（ｘ），……，a
_m-1（ｘ）のうちa_i（ｘ）だけが非零多項式であると仮
定したときのシグナチヤの値をS_i（ｘ）と表す（０≦ｉ
ｍ−１）。

次式が成立する。

S_i（ｘ）≡xⁱA_i（ｘ） modG（ｘ） …（３） S_i（ｘ）は高々（ｍ−１）次の多項式である。

入力検査系列a₀（ｘ），a₁（ｘ），……，a_m-1（ｘ）を
MISRへ入力し終えたときの値すなわちシグナチヤSIG
（ｘ）は式（３）を用いて求めることができる。すなわ
ち、MISRは線形回路でるから、a₀（ｘ），a₁（ｘ），…
…，a_m-1（ｘ）によつて生成されるS₀（ｘ），S
₁（ｘ），……，S_m-1（ｘ）の線形和がSIG（ｘ）と一致
する。すなわちが成立する。

次に入力検査パターンa₀（ｘ），a₁（ｘ），……，a_m-1
（ｘ）を行列Ａにより表す。

行列Ａは｛0,1｝を因子とするｍ×ｎ次の行列である。

被検査論理回路に誤りが含まれないときの入力検査パタ
ーンを行列Ａとする。誤りが含まれているときの入力検
査パターンを行列Ａ′とする。行列A,A′に対するシグ
ナチヤをSIG（ｘ）,SIG′（ｘ）とするとき、シンドロ
ムＹ（ｘ）を次式のとおり定義する。

Ｙ（ｘ） SIG（ｘ）＋SIG′（ｘ）modG（ｘ）…（４）Ｙ（ｘ）≠０のとき、入力検査パターンに誤りが含まれ
ていると判断し、Ｙ（ｘ）＝０のときは誤りが含まれて
いないと判断する。Ａ≠Ａ′かつＹ（ｘ）＝０となる確
率を誤り見逃し確率PMと定義する。Ａ≠Ａ′かつＹ
（ｘ）≠０となる確率を誤り検出確率PDと定義する。次
式が成り立つ。

PM＋PD＝１ ………（５）行列Ａの重みｍ（Ａ）とは行列Ａに含まれる１の個数と
定義する。ｍ（ＡＡ′）＝ｔのとき、Ａ′にｔ重誤り
が生じたと定義する。ＡＡ′は行列の各要素毎の排他
的論理和を表す。ｔ重誤りが生じる場合の数はｍ×n Ct
である。

誤り行列をＥ＝ＡＡ′と表す。行列Ｅの第ｉ行を誤り
多項式e_i（ｘ）と表す。次式が成立する。

以後、誤り行列に注目する。

多項式Ｇ（ｘ）の周期をｎと表す。これは、Ｇ（ｘ）が
割り切れることができる２項式xⁿ＋１の最小のｎの値で
与えられる。Ｇ（ｘ）がｍ次の原始多項式の場合、周期
ｎは、ｎ＝2^m−１であることが知られている。

Ｇ（ｘ）の周期をｎとし、行列Ａがｍ×ｎ次の行列とす
る。このとき次の２要素a_kl,a_k′_l′が次の（条件１）
を満たすときＧ等価と呼び、と表す。

（条件１）ｋ＋ｌ≡ｋ′＋ｌ′ mod n ２要素a_kl,a_klが（条件１）と満たさないとき、と表す。

〔補題１〕行列Ａの異なる２要素a_kl,a_k′_l′が（条件１）を満た
す（Ｇ等価でる）ものとする。このとき、行列Ａのなか
で、a_klのみが非零要素としたときのシグナチヤＳ
（ｘ）と、a_k′_l′のみが非零要素としたときのシグナ
チャＳ′（ｘ）は等しい。

（証明）行列Ａのなかでa_klのみが非零関素であるとする。a
₀（ｘ），a₁（ｘ），……，a_m-1（ｘ）のうち、a
_k（ｘ）のみが非零多項式となる。すなわち、 a_k（ｘ）＝x^l ……（５）である。a_k（ｘ）はMISRのｈ段目に入力されるから、シ
グナチヤＳ（ｘ）は次式であらわされる。

Ｓ（ｘ）≡x^k・x^l modG（ｘ）…（６） ≡x^k+l modG（ｘ）…（６′）同様に、a_klのみが非零要素であるとしたとき、次式が
成立する。

Ｓ′（ｘ）≡x^k′^+l′ modG（ｘ）…（７）条件１が成立するならば、ある整数ｂに対し、ｋ＋ｌ＝ｂ（2^m−１）k4l′ …（８）が成り立つ。また、Ｇ（ｘ）はｍ次の原始多項式であり
周期ｌは2^m−１である。すなわち、 x^2m-1≡１ modG（ｘ）…（９）である。よつて、Ｓ（ｘ）≡x^k+l modG（ｘ） ≡x^b2m-1・x^k′^+l′ modG（ｘ） ≡Ｓ′（ｘ） modG（ｘ）（10）（証明終り）が成立する。

例えば行列Ａにおいてa₀₁,a₁₀はＧ等価である。実際
a₀₁,a₁₀のみが非零である場合、すなわち、のときを考える。これを第２図で示すMISRへ入力したな
らば、a₀₁,a₁₀は、SR0とSR1の間の排他的論理和ゲート
により打ち消しあい、シグナチヤは０となる。

最も基本的なMISRとして、Ｇ（ｘ）がｍ次のGF（２）上
の原始多項式の場合を考える。Ｇ（ｘ）の周期ｎは2^m−
１となる。また検査入力パターンの長さは2^m−１とす
る。このときＧ（ｘ）はハミング符号を生成する。ハミ
ング符号は単一誤りを検出する能力がある。

（１）単一誤りが生じた場合とする。このとき、である。従つて、単一誤りは必ず検出する。

（２）２重誤りが生じた場合このとき、Ｙ（ｘ）≡x^k0×x^l0＋x^k1×ｘ^１ modG（ｘ） ≡x^k0+l0＋ｘ^k1＋１ modg（ｘ） …（10）が成立する。２個の非零要素e_ij（ｉ＝k₀,j＝l₀），
（ｉ＝k₁,j＝l₁）がＧ等価対の場合、Ｙ（ｘ）≡０、mo
dG（ｘ）となる。Ｇ等価対でない場合、k₀+l₀＜k₁+l₁と
しても、一般性を失なわない。式（10）は、Ｙ（ｘ）≡x^k0+l0（１＋ｘ^{k1＋１−（k0＋l0）}）modG
（ｘ）となる。

Ｇ（ｘ）は１＋ｘ^{k1＋１−（k0＋l0）}を割り切らない
ので、Ｇ等価対でない場合、２重誤りを検出する。

ここで２重誤り見逃し確率を計算する。

行列Ａ（ｍ×（2^m−１）次の２値行列）の中に等価対が
１組だけ含まれる組合せの数は、である。なぜなら、行列Ａのある成分に対しＧ等価な成
分がｍ個存在するからである。

２重誤りの生じる場合の数はｍ×（2^m−１）C₂であるか
ら、２重誤りが生じた時にＹ（ｘ）＝０となる確率、す
なわち、２重誤り見逃し確率PM₂はとなる。

以上のように、従来からの故障診断方式によると２重誤
りを見逃してしまう可能性があつた。

S.Z.Hassanの方式（“Using Signature Analysisto Enh
ance Testability,S.Z.Hassan著、Bookletof Abstracts
and Viewgraphs Stanford Computer Forum,Fed.198
4"）を用いても２重誤りを見逃し確率は改善されない。

〔発明の目的〕

本発明の目的は、２重誤りを100％検出する故障診断方
式を提供することにある。

〔発明の概要〕

上記目的を達成するため、逆２重比MISRという故障検出
回路を考案した。

〔発明の実施例〕

以下、本発明の実施例を図面を用いて説明する。

まず、逆２重比MISRという方式を第４図を用いて説明す
る。この方式は２個のMISR40,41（MISRG,MISRH）から成
り、しかもこれらのMISRのシフトの方向が異なることを
特徴とする。第４図において、MISRGは第２図で示したM
ISRと同一のものでる。

MISRHは第２図で示したMISRと基本的には同じ構成であ
るが、係数器の値とシフトの方向が異なる。

MISRHは次の３種類の要素から成る論理回路である。

（１）ｍ個のレジスタ（レジスタ50,51,……,52,53,5
4）すなわちSRH₀,SRH₁,SRH_m-3,SRH_m-2,SRH_m-1。

（２）（ｍ−１）個の係数器。これらはレジスタ54の
出力に係数を掛ける働きをする。すなわち係数h₁の係数
器55、係数h₂の係数器56、係数h_m-3の係数器57、係数h
_m-2の係数器58、係数h_m-1の係数器59。

（３）ｍ個の排他的論理和ゲート。すなわち排他的論
理和ゲート60,61,62,……,63,64,65。排他的論理和ゲー
ト60は入力a_m-1（ｘ）とレジスタ54の排他的論理和をと
り、レジスタ60へ伝える。排他的論理和ゲート61,62,…
…,63,64,65はそれぞれ、入力a_m-2（ｘ），a
_m-3（ｘ），a₂（ｘ），a₁（ｘ），a₀（ｘ）と前段のレ
ジスタの内容と係数器55,56,……,57,58,59の排他的論
理和をとり次段のレジスタに伝える。

MISRGによるシグナチヤをSIGG（ｘ）、MISRHによるシグ
ナチヤをSIGH（ｘ）とする。次式が成り立つ。

MISRGおよびMISRHによるシンドロームをと定義する。但し、e_i（ｘ）は誤りパターン行列の各行
を多項式で表したものである。

ここで、逆２重化MISRによれば、単一誤りおよび２重誤
りがすべて検出できることを示す。

（１）単一誤りが生じた場合MISRと同じ理由により、となり、誤りを検出する。

（２）２重誤りが生じた場合、YG（ｘ）,YH（ｘ）は
それぞれ２項または０項を含む。但し、２要素a_kl,a_kl
が同時に（条件１），（条件２）を満たすことはないか
ら、YG（ｘ）,YH（ｘ）の少なくとも一方は非零多項式
となり、２重誤りをすべて検出する。

第５図は、本発明の一実施例を示す図である。第１図で
示した検査モデルに、第４図で示した逆２重化MISR2′
を適用した。第５図で示す故障診断方式を用いれば、被
検査回路からの検査パターンa₀（ｘ），a₁（ｘ），…
…，a_m-1（ｘ）に生じた２重誤りを100％検出できる。

〔発明の効果〕本発明による逆２重化MISRを用いれば、２重誤りを必ず
検出できる。従来からのMISRでは、２重誤りを（ｍ−
１）／｛ｍ×（2^m−１）−１｝の確率で見逃していた。
したがつて本発明によれば、論理回路の故障検出確率が
向上するという効果がある。また、論理回路の故障検出
確率が高い故障診断方式を提供できる。

【図面の簡単な説明】

第１図は従来の自己テストのブロツク図、第２図，第３
図は従来のMISRの論理回路を表す図、第４図，第５図は
本発明の一実施例を示すブロツク図である。 50,51,52,53,54……レジスタ、55,56,57,58,59……係数
器、60,61,62,63,64……排他的論理和ゲート。

Claims

【特許請求の範囲】

【請求項１】検査パターンを入力する第１のフィードバ
ックシフトレジスタ及び第２のフィードバックシフトレ
ジスタと、上記第１及び第２のフィードバックシフトレジスタとそ
れぞれ所定のパターンの一致比較を行う第１及び第２の
一致検出器とを具備してなり、上記第１のフィードバックシフトレジスタはその出力端
とその入力端とを接続し、その各ステージ間には上記検
査パターンと前段のレジスタの出力と上記第１のフィー
ドバックシフトレジスタの上記出力端にその入力が接続
された係数器の出力とを入力する排他的論理和回路を設
け、上記出力端と上記入力端との間には上記検査パター
ンと出力段のレジスタの出力とを入力する排他的論理和
回路を設け、上記第２のフィードバックシフトレジスタはその出力端
とその入力端とを接続し、その各ステージ間には上記検
査パターンと前段のレジスタの出力と上記第２のフィー
ドバックシフトレジスタの上記出力端にその入力が接続
された係数器の出力とを入力する排他的論理和回路を設
け、上記出力端と上記入力端との間には上記検査パター
ンと出力段のレジスタの出力とを入力する排他的論理和
回路を設け、上記第１及び第２のフィードバックシフトレジスタは互
いに逆方向にシフトすることを特徴とする故障検出回
路。
【請求項２】故障判定回路で上記第１及び第２のフィー
ドバックシフトレジスタの内容と上記検査パターンに故
障が無い場合の期待値とが比較されて、該比較が一致す
る時に上記検査パターンに故障が無いと判断することを
特徴とする特許請求の範囲第１項に記載の故障検出回
路。