Einen Algorithmus wollen wir uns noch näher anschauen, weil er sehr interessant aufgebaut ist und auch in anderen Bereichen zum Einsatz kommt: die binäre Suche oder "Binary Search". Bislang sind wir von einer unbekannten Seriennummer ausgegangen und haben am Ende den Transponder selektiert, der sich gegen die anderen durchgesetzt hatte.
Bei der binären Suche geben wir immer enger werdende Bereiche vor, bis die gesendete Seriennummer mit der eines realen Chips übereinstimmt. Dabei nutzen wir das Verfahren einer sukzessiven Approximation, das heißt wir nähern uns schrittweise an.
Voraussetzung für eine binäre Suche ist nicht nur das Erkennen einer Kollision, sondern auch die Detektion der genauen Bit-Position des Fehlers. Aus diesem Grund kommt der Manchester-Code zum Einsatz und die Tags müssen absolut synchron antworten.
Nehmen wir für ein Beispiel an, die Transponder hätten lediglich eine 4-Bit-Seriennummer und zwar (in binärer Schreibweise)::
Der Reader sendet bei diesem Verfahren nicht nur einen Request, sondern er übergibt dem Request auch eine Bedingung und zwar im 1. Schritt:
REQUEST <= 1111
Das bedeutet so viel wie: es sollen sich alle Transponder melden, deren Seriennummer kleiner oder gleich 1111 sind. Falls sich Tags im Aktivierungsbereich befinden, wären damit alle angesprochen und alle würden antworten. Der Reader erkennt jetzt das folgende Antwortmuster: 1XX0
Aus diesem Muster kann er ableiten:
Für den weiteren Schritt berücksichtigt der Reader nur immer das höchstwertige Bit mit einer Kollision. In unserem Fall ist das Bit 2 (3. Bit von rechts). Der Reader weiß durch dieses Kollisions-Bit, dass es sowohl Tags mit einer Seriennummer geben muss, die kleiner oder gleich als 1011 sind, als auch welche, die größer oder gleich 1100 sind.
Der Reader wählt daraus wieder einen Bereich (welcher ist dem Zufall überlassen):
REQUEST <= 1011
Dieses Mal wird also Tag 1 nicht angesprochen und fällt somit aus dem Rennen. Die beiden verbleibenden Tags antworten und es ergibt sich das neue Antwortmuster: 10X0
Daraus könnte der Reader jetzt schon ableiten, dass sich lediglich zwei Transponder im Aktivierungsbereich befinden und wahllos einen davon auswählen. Wir wollen aber den nächsten Schritt zur Übung auch noch mal nach dem obigen Verfahren ermitteln.
Durch das Muster weiß der Reader, dass es Tags gibt, die kleiner oder gleich 1001 gibt, als auch welche, die größer oder gleich 1010.
Wieder entscheidet sich der Reader willkürlich für die erste Auswahl und gibt das nächste Kommando aus:
REQUEST <= 1001
Dieses Mal antwortet nur noch Tag 3 und wird für weitere Aktionen ausgewählt.
Der große Nachteil dieses Verfahren ist das hohe Datenaufkommen, denn bei jedem Schritt muss eine komplette Seriennummer übertragen werden und die ist halt 4, 7 oder sogar 10 Byte lang.
Was dabei häufig verwirrt: es geht nicht um die Tags, die sich zwischen den Grenzen befinden, sondern um eine Entscheidung, mit welcher Transponder-Gruppe wir weiter selektieren.