(57)【特許請求の範囲】
【請求項１】
不揮発性メモリに記憶され部分的に置換されたデータワードをディクリメントまたはインクリメントする２進数カウンタを実現する装置であって、
カウンタと、
作業メモリとを備え、
データワードは少なくとも２つのメモリワードの形式で不揮発性メモリに記憶され、
データワードのメモリワードを不揮発性メモリから読み取り、データワードのｋ個の置換ビットを逆再配列しながら、これらのメモリワードを作業メモリに記憶し、
逆全単写像関数をデータワードのｋ個の置換ビットに適用し、
データワードをディクリメントまたはインクリメントし、
全単写像関数をデータワードのｋ個の置換ビットに適用し、
ｋ個の置換ビットの再配列を行い、
各メモリワードに対して、それが不揮発性メモリに記憶されたメモリワードから逸脱しているかどうかをチェックし、逸脱しているメモリワードをのみを不揮発性メモリに再び記憶し、
前記全単写像関数は、写像関数が適用されるｋ個の置換ビットを表すデータワードの下位ｋビットが、写像関数適用後に、可能な限り低い頻度かつほぼ均一の頻度で、ディクリメントまたはインクリメントにより変化するようになっており、前記再配列は、作業メモリにおけるデータワードのｋ個の置換ビットを、揮発性メモリのｋ個のメモリワードに分配するように実行されることを特徴とする装置。
【請求項２】
請求項１に記載の装置において、
再配列は、メモリワードにおける位置が再配列の際に変化するこれらの置換ビットが、メモリワードの他のビットと位置を変更するように実行されることを特徴とする装置。
【請求項３】
請求項１に記載の装置において、
ディクリメントまたはインクリメントの間のステップ幅は、１であり、
置換ビットの数ｋは、データワードのメモリワード数に等しいことを特徴とする装置。
【請求項４】
請求項１に記載の装置において、
データワードは、３２ビットから成り、各メモリワードは、８ビットから成ることを特徴とする装置。
【請求項５】
請求項１に記載の装置において、
全単写像関数は、データワードの１ビットのみが、各ディクリメントまたはインクリメント毎に変化するように考えられていることを特徴とする装置。
【請求項６】
請求項１に記載の装置において、
全単写像関数は、全単写像関数が適用される前のデータワードの各値と、これに対応する全単写像関数を適用したデータワードの各値とが、対応付けられて格納された表により、実現されることを特徴とする装置。
【請求項７】
請求項１に記載の装置において、
全単写像関数は、サーチツリー法を用いることにより得られることを特徴とし、
このサーチツリー法では、
各サーチツリーレベルに対して、置換された形式のｋ個の置換ビットを含んでおり、次に高いサーチツリーレベルに対して１ビットのみが変化した、全てのこれらの実行可能な新置換ワードが導入され、
各ビットに対して、全サーチツリーレベル間の変化頻度が、記録され、各ビットに対する置換可能な最大変化頻度は、置換ビット数でカウントステップ数を割った商をまるめて、次に大きい偶数とした値に等しく、それは置換された数であり、
各レベルでは、ブランチのより高いレベルで既に生じている置換データワードは、削除されており、
最後に、ブランチの任意の１つが、選択されて、前記条件を満たしながら全レベルを通して生成することができる置換されたデータワードを実現する、ことを特徴とする装置。
【請求項８】
請求項１から７のいずれかに記載の装置の車両アクセスシステムに対する使用。
【請求項９】
請求項１から７のいずれかに記載の装置の車両アクセスシステムにおける無線キーに対する使用。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、不揮発性メモリに記憶されたデータワードをインクリメントまたはディクリメントする２進数カウンタを実現する装置に関し、その装置は、カウンタと作業メモリを備える。
【０００２】
【従来の技術】
この種の装置は、従来技術から公知であり、装置は、データワードを不揮発性メモリから読み取り、作業メモリに転送するように作動する。作業メモリにおいて、データワードは、数１（または異なる数）の２進数和によりインクリメントされ、従って、ワードのカウンタ読み取りをインクリメントする。カウンタ読み取りがインクリメントされたデータワードは、不揮発性メモリに書き戻される。１または異なる数ずつディクリメントされることも可能である。
【０００３】
この種の装置は、例えば、車両の無線キーシステムに使用され、そこでは、カウンタの２進数値は、暗号化方法により暗号化されており、無線キーにより車両に転送される。無線キーは、概して電池で作動しており、電池は、交換可能であるため、データワードのカウンタ読み取りは、内容が電池交換の際に失われないＥＥＰＲＯＭに記憶される。
【０００４】
【発明が解決しようとする課題】
しかし、とりわけデータワードの下位ビットが、データワードのカウンタ読み取りのどのディクリメントまたはインクリメントにも応答して変化し、それにより、全ての新しいカウンタ読み取りに対して、データワードの全ビットが、ＥＥＰＲＯＭに再び書き込まれなければならなくなるという問題が、生じる。これにより、メモリセルの負荷が比較的重くなり、そのメモリセルは、概してＥＥＰＲＯＭの場合には限られた書き込みサイクル数のみを見込んでおり、つまり、その耐用年数は、書き込みサイクル数により決まることを意味している。
【０００５】
本発明の目的は、ＥＥＰＲＯＭにおいて可能な限り少ない書き込みサイクル数を必要とする上述した種類の装置を提供することである。
【０００６】
【課題を解決するための手段】
この目的は、本発明により達成され、それは、不揮発性メモリに記憶された部分的に置換されたデータワードをディクリメントまたはインクリメントする２進数カウンタを実現する装置であって、カウンタと、作業メモリとを備え、データワードは少なくとも２つのメモリワードの形式で不揮発性メモリに記憶され、その装置は、
データワードのメモリワードを不揮発性メモリから読み取り、データワードのｋ個の置換ビットを逆再配列しながら、これらのメモリワードを作業メモリに記憶し、
逆全単写像関数をデータワードのｋ個の置換ビットに適用し、
データワードをディクリメントまたはインクリメントし、
全単写像関数をデータワードのｋ個の置換ビットに適用し、
ｋ個の置換ビットの再配列を行い、
各メモリワードに対して、それが不揮発性メモリに記憶されたメモリワードから逸脱しているかどうかをチェックし、逸脱しているメモリワードのみを不揮発性メモリに再び記憶し
不揮発性メモリに記憶されたデータワードをインクリメントするために、全単写像関数は、全単写像関数が適用されるｋ個の置換ビットを表すデータワードの下位ｋビットが、写像関数適用後に、可能な限り低い頻度かつほぼ均一の頻度で、ディクリメントまたはインクリメントにより変化するようになっており、再配列は、作業メモリにおけるデータワードのｋ個の置換ビットを、揮発性メモリのｋ個のメモリワードに分配するように実行される。
【０００７】
本発明の基本的な着想は、データワードをメモリにそのままではなく、つまり、変化していない形式だが部分的に置換した形式でかつ再配列したビットで、記憶することである。この文脈において置換とは、データワードのｋ個の置換ビットが、全単写像関数に適用され、不揮発性メモリにこの置換された形式で記憶されることを意味すると理解されるべきである。全単写像関数が適用されるｋ個の置換ビットの各置換ビットは、それ自体、可能な限り小さい頻度で、写像関数適用後ディクリメントまたはインクリメントのために変化し、そして全ての置換ビットは、ほぼ均一の頻度で変化するように、全単写像関数は考えられている。
【０００８】
全単写像関数の適用を受けるｋ個の置換ビットは、ｋ個のメモリワードに分配される。この文脈では、メモリワードとは、データワードを再分割した不揮発性メモリにあるワードであると理解されるべきである。
【０００９】
全単写像関数をこのように適用し、置換されたｋ個の置換ビットを再配列した結果、データワードのメモリワードが、ほぼ均一の頻度で変化する事が達成され、とりわけ全てのメモリワードが、各ディクリメントまたはインクリメント処理に応答して変化するわけではないことが達成される。全単写像関数は、実際に、統計的観点から、ディクリメントまたはインクリメント処理によりデータワードのメモリワードの各々が、ほぼ均一な頻度で変化するように考えられている。
【００１０】
しかし、これは、毎ディクリメントまたはインクリメント処理後に、ほぼひとつのメモリワードのみが、変化することを意味している。他のメモリワードは、同じ状態に維持される。従って、データワードが、全単写像関数の適用後に再書き込みされる時、作業メモリのどのメモリワードが、不揮発性メモリにある相当するメモリワードから逸脱しているかをチェックする。一般的には、１つのメモリワードのみが、逸脱している。置換ビットに全単写像関数を適用し再配列し、ディクリメントまたはインクリメントされたデータワードが、書き戻される時、なお不揮発性メモリに記憶されるメモリワードに相対して実際に変化しているメモリワードのみが、実際に書き戻される。
【００１１】
データワードの１つのメモリワードのみが、各ディクリメントまたはインクリメント処理後に不揮発性メモリに実際に書き戻される必要があり、統計的観点から、これらの書き込み処理は、データワードの全てのメモリワード間にほぼ等しく分配されることが、達成される。書き込み処理の数は、このように、不揮発性メモリの個々のワードに相対してかなり減じられる。特に、すべてのセルは、同程度に負荷される。例えば、４つのメモリワードの場合、統計的観点から、当該技術の現況に比べて、ほぼ４倍のディクリメントまたはインクリメント処理を実行可能であり、それに相当する変化データワードが、不揮発性メモリに書き込み可能である。
【００１２】
最も簡単な例では、メモリワードの置換ビットの再配列を、置換ビットをこの目的のためにメモリワードに設けられた自由な位置に書き込むことにより実行できる。しかし、メモリワードのビット幅は、その後、置換ビットにより影響をうける。これを避けるために、クレーム２に開示された本発明の解釈では、置換ビットは、メモリワードに提供された他のビットと位置を変更するようにされている。その結果、置換ビットには、どの追加記憶容量も必要としない。
【００１３】
ディクリメントまたはインクリメントする際のカウントステップの幅は、原則として、任意の数であってよい。しかし、クレーム３に開示した本発明の更なる解釈に従うと、ステップ幅は１であり、置換ビットの数ｋは、データワードのメモリワードの数に等しい。
【００１４】
ディクリメントまたはインクリメントする際のカウントステップの幅が、１に等しい場合、最適な結果は、既にデータワードのメモリワードとちょうど等しい置換ビットを提供された時に得られる。例えば、データワードが、４つのメモリワードを有する場合、最適な結果は、既にデータワードの下位４ビットが、置換ビットとして使用される時に得られる。
【００１５】
全単写像関数の上記の特性は、クレーム５に開示した更なる発明の解釈によると、毎回１ビットのみが、置換ビットに全単写像関数を適用した後の各ディクリメントまたはインクリメント処理に応答して変化する時に、実現する。これは、また、１つのメモリワードのみが、以前のカウンタ読み取りに相対して変化しており、このメモリワードのみを不揮発性メモリに再び書き込まなければならないことも意味している。
【００１６】
本発明の更なる解釈によると、全単写像関数は、４つの置換ビットが、置換されない形式で記憶されている表を、生成するように、有利に実現できる。４つのデータワードは、擬似的に表現されており、カウンタデータワードには等しくはなく、それに対して、毎回４つの置換ビットのうち１つのデータワードを、置換された形式で表に示すことができる。全単写像関数は、このように、この表の適用により実現できる。
【００１７】
全単写像関数は、原則として、試行錯誤により生成することができる。それは、ｋ個の置換ビットの間で毎回１ビットのみが、ディクリメントまたはインクリメントの際に全単写像関数の適用により変化するというように考えられている。全単写像関数を生成する有利な方法は、クレーム７に開示される本発明の更なる解釈によると、サーチツリー法を用いることに特徴付けられる。このようなサーチツリーでは、ｋ個の置換ビットは、置換された形式で、各レベルに対する置換ワードとして、常に入れられる。サーチツリーでは、新しいレベルが、ｋ個の置換ビットを有する置換ワードに始まり毎回形成され、これらのビットのうちひとつのみが、新しいレベルについて変化している場合、ｋ個の置換ビットを有する新しい置換ビットが入れられる。このように、ｋ個の置換ビットのうち１ビットのみが、常にレベル毎に変化しているサーチツリーのブランチを形成することが可能となる。この点について、既により高いレベルで生成されていた新しく入ったｋ個の置換ビットの置換ワードは、削除されることを述べておく。さらに、変化頻度は、サーチツリーのブランチにおけるｋ個の置換ビットの各ビットに対して記録されなければならならず、それは、ｋ個の置換ビットの各ビットは、サーチツリーの完全なブランチでは、ｋ回のみ変化されている可能性があるからであることを述べておく。
【００１８】
このようにしてサーチツリーが生成される時、ブランチには、もともと早く終了させられたものがあり、それは、上記要件が、その関係するブランチについては満たされていないからである。しかし、実行可能な全２ｋレベルを生成可能なブランチも存在する。これらの全条件を満たしたブランチに則して、ｋ個の置換ビットの置換ワードとして使用可能な一連のデータワードが、生成される。そして、置換ワードのｋ個の置換ビットに対して、例えば、表にもとづいて、ディクリメントまたはインクリメントされた置換ワードのｋ個の置換ビットが、どのように置換データワードのビットに全単写像関数の適用の際に転送されるかが、定義される。
【００１９】
【発明の実施の形態】
本発明の実施形態を以下に図面の１つの図を参照にして詳細に説明する。
【００２０】
不揮発性メモリは、ＥＥＰＲＯＭであり、ディクリメントまたはインクリメントされるデータワードを記憶する。ディクリメントまたはインクリメントするために、原則的にカウント処理を任意のステップ幅で実行するが、ステップ幅は、通常１である。以下では、メモリ１に記憶されるデータワードは、３２ビットのビット幅を有し、不揮発性メモリ１に各８ビットの４メモリワードの形式で記憶されると仮定する。さらに、以下では、各カウント処理（以下で詳細に説明する）は、データワードを１に等しいステップ幅でインクリメントすることに関するとも仮定する。従って、全てのインクリメント処理において、デジタルナンバー１が、データワードに付加される。
【００２１】
このようなカウント処理を可能にするために、図に示す装置は、作業メモリ２を備える。その装置には、好ましくはマイクロプロセッサである制御回路３も備えられている。
【００２２】
当該技術の現況から公知であるこの種の装置において、不揮発性メモリ１に記憶されるデータワードのインクリメントは、データワードを不揮発性メモリ１から作業メモリ２に転送し、作業メモリ２においてデータワードをインクリメントし、続いて不揮発性メモリ１に再び書き込むというように実現される。この処理は、制御回路３により制御される。
【００２３】
当該技術の現況から公知である解決策によると、作業メモリ２における各インクリメント処理により、データワードの下位ビットを含むメモリワードのビットが、毎インクリメント処理後に変化するため、いずれの場合でもこのメモリワードを、不揮発性メモリ１に各インクリメント処理後に再び書き込まなければならないという問題が生じる。
【００２４】
しかし、不揮発性メモリ、例えば、ＥＥＰＲＯＭは、限られた書き込みサイクル数のみを見込んでいるという問題がある。従って、目的は、不揮発性メモリの各メモリセルについて書き込みサイクル数を可能な限り小さく保つことである。
【００２５】
従って、本発明による装置において、作業メモリ２から不揮発性メモリ１に再書き込みする前に、データワードの下位ｋビットに全単写像関数を適用し、本例においてこれらのビットを均一にデータワードの４メモリワードに分配するようにする。以下に詳細に記述するように、各インクリメント処理において１つのメモリワードのみが、データワードにおいて既に置換された置換ビットに変更することが、このようにして達成される。既に置換された置換ビットを含む４つのメモリワードを有するデータワードが、不揮発性メモリ１に書き戻された時、制御回路３は、しばらくの間作業メモリ２になお記憶されているこれらのメモリワードのどれが、不揮発性メモリ１に記憶されているメモリワードから、逸脱しているかをチェックする。変化したメモリワードのみを不揮発性メモリ１に再び書き込む。
【００２６】
インクリメント処理を実行し全単写像関数を置換ビットに適用した後に、置換ビットが、可能な限り少ない頻度で変化し、それら全てが、ほぼ均一の頻度で変化するように全単写像関数は考えられているので、８ビットの４つのメモリワードに関係する本例において、作業メモリ２から不揮発性メモリ１へ再書き込みする際にインクリメント処理毎にほぼ１つのメモリワードのみを不揮発性メモリに再び書き込めばよいことが達成される。さらに統計的な観点から、４つのメモリワードの全ては、この再書き込み処理にほぼ均一の頻度で関与する。置換した形の置換ビットは、ほぼ均一の頻度で変化するため、４つのメモリワードも、再書き込み処理にほぼ均一の頻度で関与することも達成されている。
【００２７】
図に示す本発明による装置の処理を以下に詳細に記述する。
【００２８】
インクリメントされ４つの置換した置換ビットからなるデータワードは、不揮発性メモリ１に記憶される。データワードをインクリメントするために、それは、不揮発性メモリ１から作業メモリ２にロードされる。置換ビットは、データワード内の新しい位置にシフトしているが、その初期位置に再びシフトし、逆全単写像関数が適用され、それにより置換した置換ビットが、その置換していない初期値に再び変換されて戻る。その後、データワードは、交換していない形式で作業メモリにおいて再び利用可能となり、その形式は、部分的に置換したり再配列したりされていない形式である。その後、このデータワードは、作業メモリ２において制御回路３によりインクリメント可能となる。このインクリメント処理の後、本例では、データワードの４つの置換ビットに、全単写像関数を適用しており、それを以下に詳細に記述する。これらの４つの置換ビットは、データワードの下位４ビットである。この置換処理の後、４つの置換された置換ビットは、均一に４つのメモリワードに分配され、つまり、置換ビットの各々は、メモリワードの１つにおいてシフトされる。そのため、メモリワードの対応する位置に存在した他のビットと交換するのに有利である。
【００２９】
従って、この再配列処理の後に各メモリワードは、１つの置換ビットを含む。全単写像関数の概念のため、本例におけるこれらの置換ビットの各々は、ほぼ４回毎のインクリメント処理後に変化する。４つの置換ビットは、データワードの下位ビットであり、よって最も頻繁に変化するビットであるため、４つの置換された置換ビットは、４つのメモリワードに分配されており、メモリワードが変化する頻度を決定する。４つの置換ビット全てが、再びほぼ均一の頻度で、つまりほぼ４回のインクリメント処理毎に変化するので、４つのメモリワードのほぼ１つのみが、各インクリメント処理の後に変化するのみとなり、この変化の頻度が、均一に４つのメモリワードに分配されるということが、４つのメモリワードについて達成される。
【００３０】
不揮発性メモリ１における書き込み処理の数を実際に減じるために、置換された形式で置換ビットが存在するメモリワードを再書き込みする前に、これらのメモリワードが、直前のインクリメント処理の結果として不揮発性メモリ１になお記憶されているメモリワードに相対して実際に変化したかを、チェックする。新たに形成されたメモリワードについての作業メモリ２から不揮発性メモリ１への再書き込み処理は、実際に変化したメモリワードに対してのみ行われる。従って、上述の理由のため、統計的観点から４つのメモリワードのうち１つのみを不揮発性メモリ１に各カウント処理後に再書き込みすることが必要となる。このように、不揮発性メモリ１の個々のメモリセルに対して、ほぼ４という因数により書き込み処理を減じることが、当該技術の現況から公知の解決策に比べて達成されている。不揮発性メモリ１の耐用年数を同様の因数によりのばすことが、このように達成されており、つまり、不揮発性メモリ１の耐用年数に対してほぼ４倍のインクリメント処理を実行可能となる。
【００３１】
置換と再配列の実行を、以下にいくつかの数学的な表現をもとに再び説明する。
【００３２】
式（１）は、
【数１】
0004157940.tif 000002
例えば、作業メモリ２に存在する時の３２ビットのデータワードを表す。このデータワードは、置換されておらず、あるいはもっと正確に表現すると、データワードのどのビットも置換されていない。このデータワードＣは、その値がインクリメントされるデータワードである。ビットＣ０は、最下位ビットであり、Ｃ３１は、最上位ビットである。少なくとも最下位ビットＣ０は、各カウント処理の間に変化する。個々のビットにおける変化の頻度は、最上位ビットＣ３１から最下位ビットＣ０の方向に向けて増加する。これは、最下位ビットは、最も頻繁に変化することを意味する。式１に従うデータワードＣは、図に示す不揮発性メモリ１に再書き込みされる、つまり、インクリメントの後毎回、非常に大きな書き込みロードが、最下位ビットを含むメモリワードに対して生じており、それは、最下位ビットが、毎インクリメント処理後に変化し、よって毎回書き込み処理が不揮発性メモリ１において必要とされるからである。この問題を避けるために、本発明による装置は、置換と再配列に関係している。
【００３３】
本例において、式１に従うデータワードＣは、不揮発性メモリ１に再書き込みされる際に４つのメモリワードに再分割される。これらの４つのメモリワードに対してほぼ均一の変化頻度を達成するために、式１に従うデータワードの４つの最下位ビットに、全単写像関数が適用され、つまり、置換される。式２は、ｋビットに対する一般的な形式においてこれが置換される様子を説明する。
【００３４】
【数２】
0004157940.tif 000003
（ｋ＝置換されるビット数）
本例において、ｋは４に等しくあるべきであり、それは、データワードが、４つのメモリワードに再分割されると共に４つの置換ビットが、既に４つのメモリワードに対する最適な結果を与えているからである。
【００３５】
【数３】
0004157940.tif 000004
置換処理は、カウンタワードをインクリメントした後のみ行われる。式４は、
【数４】
0004157940.tif 000005
データワードをインクリメントした後に、データワードＣの４つのビットＣ０からＣ３に全単写像関数を適用することにより生じた４つの置換ビットＰ０からＰ３を示す。全単写像関数は、置換された形式の４つの置換ビットＰ０からＰ３が、インクリメント処理の影響下でほぼ均一の頻度で変化するように構成されている。本例については、４つの置換ビットに関連しており、これは、毎回のデータワードＣのカウント処理及びデータワードＣの４つのビットＣ０からＣ３への全単写像関数の適用の後に、置換された形式での置換ビットを含む、置換されたデータワードＣ’を生じており、４つの置換ビットＰ０からＰ３のうちほぼ１つのみが、統計的観点から変化していることを意味する。
【００３６】
このようにこの置換された形式での４つの下位ビットは、ほぼ等しい変化の頻度を表すようになっている。
【００３７】
４つの置換ビットのこの特性を最適に用いるために、４つの置換ビットＰ０からＰ３は、データワードの４つのメモリワードに分配され、つまり、毎回１つの置換された置換ビットが、４つのメモリワードの各々にセットされる。
【００３８】
この結果、式５に従うメモリワードＥ’０からＥ’３の構造となる。
【００３９】
【数５】
0004157940.tif 000006
式５は、４つのメモリワードＥ’０からＥ’３の各々が、１つの置換ビットＰ０、Ｐ１、Ｐ２、または、Ｐ３を含むことを示す。置換ビットは、他のビットの位置へシフトしており、その他のビット自体は、置換ビットの初期位置にシフトしている。これらのビットの位置は、このように交換されている。式５において、この交換をメモリワードＥ’３に認めることができ、そこでは、メモリワードＥ０、Ｅ１、Ｅ２にもともと存在していたビットＥ８、Ｅ１６、Ｅ２４が、再配列の結果、今はメモリワードＥ’３に存在している。
【００４０】
この置換と置換されたビットＰ０からＰ３の再配列のため、式５に従う４つのメモリワードＥ’０からＥ’３は、全単写像関数適用後に、そして続く再配列の後につまり、式５に示された形式で、ほぼ均一の頻度で毎インクリメント処理後に変化するという特性を有している。
【００４１】
これらの処理後、式５に従って４つのメモリワードから生成されたデータワードは、図に示すように不揮発性メモリ１に再び書き込まれる。しかし、メモリワードＥ’０からＥ’３の説明した特性のために、統計的観点からは、これらのメモリワードの１つのみが、不揮発性メモリ１に記憶された以前のカウンタ読み取りに記憶されるメモリワードに比較して変化する。従って再書き込み処理の間、実際に変化したメモリワードＥ’０、Ｅ’１、Ｅ’２、または、Ｅ’３のみが、不揮発性メモリ１に再書き込みされる。
【００４２】
書き込み処理数は、このように、４という因数により減じられ、よって不揮発性メモリ１の耐用年数は、それに従って延長する。
【００４３】
このように、この書き込み処理後、不揮発性メモリ１は、１つのメモリワードのみが、変化している可能性のある新データワードを含む。このデータワードは、そこに存在するが、置換された形式、つまり、４つの置換ビットが、置換された形式に現われている形式である。さらに、これらのビットは、再配列されている。作業メモリ２における次のカウント処理のために、このデータワードは、不揮発性メモリ１から読み出されなければならず、インクリメントプロセスの実行前に、置換ビットは、もともとの位置に再びシフトされていなければならない。当然、同様のことが、置換ビットと位置を変更したビットについてもあてはまる。さらに４つの置換ビットＰ０からＰ３の置換は、逆全単写像関数の適用により、再びキャンセルされ、それにより、下位ビットＣ０からＣ３は、再び作業メモリ２にもとの形式で存在することとなる。制御回路３による作業メモリ２でのデータワードのインクリメント処理は、その後にのみ実行可能である。インクリメント処理実行後、作業メモリ２は、再び新データワードＣを含み、その新データワードＣには上述の処理が繰り返される。
【００４４】
全単写像関数（置換とも称する）の特性を以下に詳細に説明する。この説明を以下の表１を参照に行う。
【００４５】
【表１】
0004157940.tif 000007
表の最初の列は、式１に従うデータワードの下位４ビットを示す。既に述べた通り、インクリメントは、１に等しいカウントステップ幅で実行される仮定されている。表の最初の４列は、下位４ビットＣ０からＣ３がどのようにインクリメントされるかを示している。これらの下位４ビットは、式１に従うデータワードＣ内のビットであり、それは、最も頻繁に変化し、よって不揮発性メモリ１への書き込み頻度を決定するものである。
【００４６】
表の右側にある４つの列は、置換された形式で４つの置換ビットをＰ０からＰ３として示している。表では、表の１ライン上において、左側にある４つのビットは、置換されていない形式で入っており、右側のものは、置換された形式で入っている。言い換えれば、表の左側に示された４つのビットＣ０からＣ３は、全単写像関数を適用された時、表の右側に示された置換ビットＰ０からＰ３に変換される。同様に、逆全単写像関数では、４つの置換ビットは、そのもともとの値に表により変換されて戻る。
【００４７】
置換ビットＰ０からＰ３に、よって全単写像関数の特性に課された必要条件は、統計的観点からすると、毎回、４つの置換ビットＰ０からＰ３の１つのみが、インクリメント処理の実行後、変化するということである。
【００４８】
このことを上に示した表をもとに簡単に証明することができる。
【００４９】
表の左側の部分は、４つの置換されていない下位ビットＣ０からＣ３を１６カウントステップにおいて示している。
【００５０】
表の右側の部分は、同じビットを置換された形式で置換ビットＰ０からＰ３として示している。１データセットから他のデータセットへの間に、置換ビットＰ０からＰ３の１つのビットのみが、各インクリメント処理後に変化していることがわかる。例えば、表に示された１行目から２行目では、ビットＰ０のみが、変化している。表の２行目から３行目では、ビットＰ１のみが変化している。同じことが、表に従って各カウンタステップに起きる。１６カウントステップの全サイクルの間、置換ビットＰ０からＰ３の各々は、ちょうど４回変化していることもわかる。このように、この置換により、毎カウントステップ後に、下位４ビットＣ０からＣ３が、全単写像関数の適用の後に、置換された形式で置換ビットＰ０からＰ３として同じ頻度で変化すると共に、各カウントステップにおいて、毎回これらの置換ビットＰ０からＰ３のうち１つのみが、変化することが保証される。
【００５１】
表１に示すように下位ビットＣ０からＣ３を置換されたビットＰ０からＰ３に置換することは、原則として試行錯誤により実現でき、つまり、表の右側部分に置換ビットが現われることは、置換ビットＰ０からＰ３が上記条件を満たす限り原則として任意におきるかもしれないことを意味する。全単写像関数の構成について系統的あるいは数学的な規則を示すことは、不可能であるとわかっている。このような全単写の規則の構成を一般的に有効に記述する一般的な数式は、知られていない。
【００５２】
（表の右側部分に示すような）置換ビットＰ０からＰ３の一連のデータワードを得るためには、サーチツリーを使うことにより、不十分だが系統的になる可能性がある。まず、例えば、置換ビットの第１データワードから、ビット００００を用いてサーチツリーを形成し、このサーチツリーでは、新データワードを各新レベルに入れ、そこでは、新データワードの１ビットのみが、直前レベルの置換ワードをもとに毎回変化する。このように、連続して新しいレベルが、置換ワードと共に形成され、そのワードでは、１ビットのみが、直前のレベルに比べて変化している。このように、表の右側部分に従って形成された置換ワードのブランチに則してサーチツリーを解釈することが、可能である。しかし、サーチツリーの各ブランチに対して、及び、各置換されたビットに対して、ルートから始まりこのような遠くまでの全サーチツリーレベル間での変化頻度を記録すべきことを述べておく。各ビットに対する置換可能な最大変化頻度は、カウントステップ数を置換ビット数で割った商をまるめて、次に大きな偶数としたものと等しい。４つの置換ビット、よって１６の実行可能なカウントステップの場合、従って、４という値が、変化の最大頻度として得られる。この値を超えた時、ツリーのこのブランチにおけるサーチは、終了する。さらに、サーチツリーのブランチの各レベルでは、ブランチのより高いレベルにおいて既に存在している置換ワードが、削除される。このように、いくつかのブランチは、不適切なものとなり、サーチツリーを形成する間に既に終了しているものもある。なぜなら、これらのブランチが、これらの条件を満たさないからである。しかし、サーチツリーが完成した後、前記条件を満たすブランチも存在する。このようなブランチに則した置換ワードは、その後、表の右側部分の置換ワードを表す。例えば、４つの置換ビットに対して、これらのワードは、１６データワードであり、それらは、その後サーチツリーのブランチに則して位置決めされる。これらの置換ワードは、その後、上の表に従って全単写像関数のために使用される。これは、置換ワードは、表１について上述したように、もともとの下位ビットＣ０からＣ３を表に従って置き換わることを、まさに意味する。
【００５３】
このように、サーチツリー法を使用することにより、置換データワードを系統的に得ることができる。全単写像関数は、その後、上記の表に従って、つまり、４つの下位ビットＣ０からＣ３の各集まりに対して、置換ビットＰ０からＰ３、つまり、置換ワードの、対応する集まりが特定されるという方法で得られる。
【００５４】
本発明による装置は、いわゆるエスケープ方法で作動する車両の無線キーシステムに有利に用いることができる。無線キーにおける十分に大きなカウンタ（本例では３２ビット）は、その後、キーを押す毎に応答してインクリメントされる。カウンタの２進数値は、その後、暗号化方法により暗号化される。カウンタ読み取りに関してこのように得られた暗号化情報は、車両に適用される。車両の論理ユニットは、その後、送信された暗号化情報の正確性を、瞬間カウンタ読み取りと暗号化アルゴリズムの情報をもとに検証し、それにより、関連する機能をアクティブにできる。この種の無線キーは、電池で作動しており、図に従う不揮発性メモリ１は、ＥＥＰＲＯＭとして構成されており、従って無線キーの内容が、電池交換時に失われないようになっている。しかし、この種のＥＥＰＲＯＭは、可能な書き込み処理の数と、よってこのようなシステムの耐用年数も制限されているという欠点を有する。上述の通り、本発明による装置により、例えば、ＥＥＰＲＯＭにおける３２ビットのデータワードと８ビットのメモリワードの例では、４という因数による書き込み処理数の減少と、よって相当する無線キーにおけるシステム耐用年数の延長を可能にする。
【図面の簡単な説明】
【図１】図１は、本発明による、不揮発性メモリ１を含む装置の構成図を示す。
【符号の説明】
１  不揮発性メモリ
２  作業メモリ
３  制御回路
【図１】
0004157940.tif 000008