符号理論の手法に基づくシグネチャ検査法の性能評価

基于编码理论技术的签名校验方法的性能评估

• 批准号: 05750344
• 负责人: 藤原 融
• 金额: $ 0.58万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1993
• 资助国家: 日本
• 起止时间: 1993 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-05750344/
• 关键词: シグネシャ検査法; 故障見逃し確率; ハミング符号; BCH符号; 重み分布; 誤り見逃し確率

大規模集積回路の自己検査法で用いられるシグネシャ検査法において,圧縮のために故障を見逃す確率(故障見逃し確率)の評価に関して,符号理論の手法を適用することにより,以下のような結果を得た.1)検査出力の誤りはランダムであると仮定する.そのビット誤り率epsilonが実際にどの程度かよくわからない場合も多いので,0<epsilon<1/2や0<epsilon<1における故障見逃し確率の最大値を主たる評価基準として,16次の原始多項式とBCH多項式(2重誤り訂正BCH符号の生成多項式)に基づくすべての単一入力シグネチャレジスタの性能評価を各種のテスト長に対して行った.その結果,原始多項式のほうが最大値にばらつきが大きく,最悪の場合1000倍程度悪いことを示した.一方BCH多項式では5倍程度であった.これは,対応符号の最大重みに大きく影響され,ハミング符号では大きな重みの符号語が存在する可能性が高いためである.2)段数が32の場合,正確な故障見逃し確率を求めることは困難である.一般の符号に対して大きな重みの符号語数を効率よく計算する方法を考案し,それを用いて下界を評価した.それにより一部の原始多項式について故障見逃し確率が極めて大きいことを示した.またBCH多項式の場合その周期より1だけ短いテスト長における対応符号の重み分布公式を明らかにした.最大重みは符号長-4以下であるので,このテスト長の場合BCH多項式がよいことがわかった.(3)生成多項式(X-alpha)のリ-ドソロモン符号符号に基づく,多入力レジスタの場合,従来よく用いられている多項式基底の場合に2元重み2の符号語数が最も大きくなることを示した.また,32段階程度の場合,実力的なテスト長(符号長)で,最小距離を3にする基底の構成法も見い出した.そのような基底のうちでハードウエア量の少なくなるものを計算機探索した.その結果,最悪時の約半分のものを見出した.

The self-detection method of large-scale integrated circuits is used to evaluate the failure detection accuracy of compression and compression, and the method of symbol theory is applied to the evaluation. The following results are obtained. 1) The error detection of detection force is determined. The error rate epsilon is the maximum error rate in many cases, 0 <epsilon<1/2 or 0<epsilon<1. The evaluation criterion is the primitive polynomial of degree 16 and the BCH polynomial (generator polynomial with double error correction BCH symbol). As a result, the primitive polynomial has a maximum value of A square BCH polynomial 5 times the degree. The maximum weight of the symbol has a large impact on the symbol. The probability of the symbol being large is high. The number of segments is 32. The correct failure rate is difficult to find. General symbol number calculation method is examined, and the lower bound of the symbol number is evaluated. The probability of failure is very high, and the probability of failure is very high. In the case of BCH polynomials, the period is 1 minute, the length is 1 minute, the sign is 1 minute, and the distribution formula is 1 minute. The maximum weight (3)Generator Polynomials (X-alpha) are multi-dimensional polynomial bases, where the number of symbols of 2-ary weight is the largest. In the case of 32 steps, the minimum distance of the force is 3 and the base composition method is 3. The computer explores the base of the game. As a result, the most timely and about half of the time to see out.

项目成果

Shou-ping Feng, Toru Fujiwara Takao Kasami, Kazuhiko Iwasaki: "On the maximum Value of aliasing probabilities for single input signatuce registers" IEEE Transactions on Computers. 43 (to appear). (1994)

Shou-ping Feng、Toru Fujiwara Takao Kasami、Kazuhiko Iwasaki：“论单输入签名寄存器的混叠概率的最大值”IEEE Transactions on Computers。