Jste zde

Algoritmus procházení sběrnice 1-Wire

Redakce HW serveru, 14. Březen 2005 - 0:00

Článek popisuje algoritmus, pomocí kterého lze určit, kolik zařízení je připojeno ke sběrnici

1-Wire? a zjistit jejich typ a identifikátor.

Úvod

Každé 1-Wire™ zařízení, u kterého to dává smysl (iButton, teploměry, převodníky apod.), má v sobě paměť ROM, která obsahuje 64bitové unikátní číslo, pomocí kterého je možné jednotlivá zařízení na sběrnici od sebe navzájem odlišit. Toto číslo se skládá z typu zařízení (spodních 8 bitů, kódy jsou uvedeny v Application Note 155), sériového čísla (48 bitů) a z CRC kódu (nejvyšších 8 bitů). Pomocí tohoto čísla je každé zařízení jednoznačně identifikovatelné. Při komunikaci s konkrétním zařízením je třeba po RESET pulsu vyslat příkaz Match ROM, pak 64bitový kód zařízení, se kterým se má pracovat, a teprve poté poslat příkaz.

Na 1-Wire™ sběrnici může být paralelně připojeno více 1-Wire™ zařízení, např. několik tepelných čidel DS18B20 spolu s pamětí DS2431 a A/D převodníkem DS2450. Výhoda je zřejmá - mezi masterem (např. PC) a snímači vystačíme s pouhými dvěma vodiči.

1Wire sbernice

Více zařízení připojených na 1-Wire™ sběrnici


V následujícím textu popíšu způsob, jakým lze projít celou 1-Wire™ sběrnici a zjistit identifikační kódy jednotlivých připojených zařízení. Algoritmus je popsán v Application Note 187: 1-Wire Search Algorithm. Jde o tzv. algoritmus prohledávání binárního stromu. Jeho minimální verzi popíšu v následujícím textu.

Příkazy SEARCH a ALARM SEARCH

Většina 1-Wire™ zařízení implementuje příkaz SEARCH (kód 0xF0). Zařízení, která mohou být v nějakém "poplachovém stavu" implementují i příkaz ALARM SEARCH (kód 0xEC). Tento příkaz se od předchozího liší pouze tím, že na něj reagují zařízení, které jsou momentálně v "poplachovém stavu" (teplotní čidlo, u něhož je překročena nastavená hranice teploty apod.), což umožňuje rychleji zjistit, které zařízení má být obslouženo.

Zařízení, které přijme SEARCH příkaz, odpoví tím, že vyšle první (nejnižší) bit svého 64bitového kódu. Je-li na sběrnici víc oslovených zařízení, odpoví všechny naráz. Jak vyplývá ze specifikace 1-Wire™ sběrnice (zařízení jsou připojena paralelně ke společnému vodiči výstupem s otevřeným kolektorem), výsledkem je logický součin (AND) všech bitů. Po vyslání tohoto bitu požádá master o vyslání dalšího bitu. Zařízení na tento požadavek odpoví negací prve vyslaného bitu. Z těchto dvou přijatých bitů lze odvodit situaci na sběrnici. Mohou nastat čtyři různé možnosti:

První bitDruhý bitSituace
0 0 Na sběrnici je více zařízení. Tato zařízení mají na tomto místě ve svých kódech různé hodnoty. Došlo k neshodě.
0 1 Na sběrnici je jedno či více zařízení. Tato zařízení mají na tomto místě ve svých kódech bit s hodnotou 0.
1 0 Na sběrnici je jedno či více zařízení. Tato zařízení mají na tomto místě ve svých kódech bit s hodnotou 1.
1 1 Na sběrnici není žádné zařízení, které by reagovalo na příkaz SEARCH.

Master nyní vyšle jeden potvrzovací bit. Dále se budou vyhledávání účastnit pouze zařízení, které mají na prvním místě bit s hodnotou stejnou jako vyslal master.

Pokud mají všechna zařízení na dané pozici stejnou hodnotu bitu, vyšle master tuto hodnotu. Pokud mají různé hodnoty (tzn. nastala první možnost - oba přečtené bity byly nulové), musí si master poznamenat, na které pozici došlo k neshodě, a vyšle buď 1 nebo 0. Zda master vyšle 0 nebo 1 určí na základě předchozích hledání, především pozice poslední nalezené neshody. Dále popsaný algoritmus vysílá nejprve nulu a při druhém průchodu vysílá jedničku.

Tento postup se opakuje, dokud není načteno všech 64 bitů identifikace. Pokud při načítání došlo k neshodě v nějakém bitu, znamená to, že je na sběrnici více zařízení a celý postup se opakuje s tím, že na pozici poslední neshody se nyní vysílá bit opačné hodnoty (prochází se "druhá větev").

Popis algoritmu

Procházení sběrnice sestává z opakovaných hledání jednotlivých zařízení. V každém cyklu je nalezeno jedno zařízení. V algoritmu je třeba si neustále udržovat informaci o kódu posledního nalezeného zařízení a o pozici neshody (pokud k nějaké došlo, pokud k žádné nedošlo, je nalezené zařízení na sběrnici samo).

Algoritmus pracuje s následujícími proměnnými:

id_bit_number - Pořadové číslo bitu, který je právě prohledáván (1 - 64).
id_bit - Bit přečtený jako první. Jeho hodnota je logický součin všech bitů na pozici id_bit_number ze všech zařízení, které se účastní vyhledávání.
cmp_id_bit - Bit přečtený jako druhý, doplněk id_bit.
LastDiscrepancy - Hodnota udávající pořadové číslo bitu, u něhož došlo při posledním hledání k neshodě.
LastDeviceFlag - Příznak posledního nalezeného zařízení.
Last_Zero - Hodnota udávající pořadové číslo bitu, u něhož došlo při aktuálním hledání k neshodě, ze které bylo pokračováno odpovědí "0".
ROM_NO - Buffer o velikosti 64 bitů (8 byte), který obsahuje aktuálně načítané číslo zařízení
search_direction Bitová proměnná, udávající směr dalšího hledání. Zařízení, která mají bit na pozici id_bit_number roven této hodnotě se budou dále účastnit prohledávání, ostatní zařízení přestanou komunikovat až do vyslání RESET pulsu.

Před prvním hledáním (funkce FIRST) je proměnná LastDiscrepancy vynulována. Po volání hledací rutiny je v ROM_NO číslo nalezeného zařízení. Pokud není žádné zařízení nalezeno, je hledání ukončeno s chybou.

Hledání dalšího zařízení (funkce NEXT) využívá hodnoty z prvního hledání, uložené v proměnných ROM_NO a LastDiscrepancy. "Hledací" rutina vrátí v ROM_NO číslo dalšího zařízení, nebo, bylo-li předcházející nalezené zařízení posledním, vrátí chybový kód.

Hledání jednotlivých zařízení začíná tím, že master vyšle RESET puls a čeká na potvrzení PRESENCE pulsem. Pokud přijde, hledání může pokračovat a jsou nastaveny proměnné: id_bit_number (pozice zpracovávaného bitu) na hodnotu 1 a last_zero (pozice poslední odpovědi "0" na zjištěnou neshodu) na hodnotu 0. Poté je vyslán příkaz SEARCH nebo ALARM SEARCH. Následuje smyčka, v níž je skládán obsah ROM_NO. Tato smyčka se opakuje 64krát, tedy pro každý bit identifikačního kódu.

Ve smyčce jsou nejprve přečteny dva bity (zařízení vysílá vždy hodnotu bitu a její doplněk), viz výše. Pokud se od sebe oba přijaté bity liší (což znamená, že všechna zařízení na dané pozici mají stejnou hodnotu bitu), je hodnota prvního zapsána do ROM_NO na pozici danou id_bit_number a jeho hodnota je zároveň zapsána do search_direction. Pokud jsou oba jedničkové, znamená to, že žádné zařízení na hledání neodpovídá a funkce končí. Pokud jsou oba nulové, znamená to, že je třeba se rozhodnout, jestli bude vyslána nula nebo jednička. Rozhoduje se na základě proměnných LastDiscrepancy a id_bit_number takto:

LastDiscrepancy vs. id_bit_numberReakce
id_bit_number > LastDiscrepancy Last_zero = id_bit_number
search_direction = 0
id_bit_number == LastDiscrepancy search_direction = 1
id_bit_number < LastDiscrepancy search_direction = (ROM_NO & (1 << id_bit_number) > 0)
(search_direction je nastavena na hodnotu bitu na stejné pozici v předchozím nalezeném ROM_NO)

Následně je vyslána hodnota bitu search_direction, tento bit je zapsán do ROM_NO na odpovídající pozici a je zvýšeno počítadlo id_bit_number. Pak se celá smyčka opakuje.

Po zjištění všech bitů je do proměnné LastDiscrepancy zapsána hodnota proměnné LastZero. Pokud je tato hodnota nulová, znamená to, že je nalezené zařízení poslední.

Ukázka práce algoritmu

Postup procházení demonstruji pro zjednodušení na hledání tří zařízení s dvoubitovými kódy. Mějme zařízení A s kódem 01, zařízení B s kódem 00 a zařízení C s kódem 11.

Procházení binárního stromu

Ilustrace k ukázce práce hledacího algoritmu.


FIRST

  • LastDiscrepancy = 0
  • Master vyšle RESET puls a čeká na PRESENCE puls. Pokud není PRESENCE, funkce končí
  • id_bit_number = 1; last_zero = 0
  • Master vyšle příkaz SEARCH (0xF0)
  • Master přečte bit ze sběrnice do proměnné id_bit, jehož hodnota bude "1 (zařízení A) AND 0 (zařízení B) AND 1 (zařízení C)" = 0
  • Master přečte další bit ze sběrnice do proměnné cmp_id_bit - jeho hodnota bude "0 (zařízení A) AND 1 (zařízení B) AND 0 (zařízení C)" = 0
  • Došlo k neshodě, protože id_bit == 0 a cmp_id_bit == 0
  • Protože id_bit_number > LastDiscrepancy, tak je search_direction nastaveno na hodnotu 0, Last_Zero na hodnotu id_bit_number (tedy 1)
  • Hodnota search_direction je přidána do ROM_NO
  • Master vyšle hodnotu z search_direction (0) na sběrnici. Dalšího vyhledávání se tedy budou účastnit pouze zařízení, které mají na pozici nejnižšího bitu hodnotu 0 (zařízení B), ostatní (A a C) přejdou do čekacího módu
  • Hodnota id_bit_number je zvýšena o 1
  • Master přečte bit do id_bit, jeho hodnota bude 0 (odpovídá pouze zařízení B).
  • Master přečte doplňkový bit do cmp_id_bit, jeho hodnota bude 1 (odpovídá pouze zařízení B).
  • Protože hodnoty id_bit a cmp_id_bit jsou různé, znamená to, že nedošlo k neshodě.
  • Proměnná search_direction je nastavena na hodnotu proměnné id_bit (0)
  • Hodnota search_direction je přidána do ROM_NO
  • Master vyšle hodnotu z search_direction (0) na sběrnici.
  • Bylo zjištěno první zařízení (zařízení B, ROM_NO == 00). Zařízení je nyní vybráno a je mu možno vyslat příkaz
  • LastDiscrepancy = LastZero(1)

NEXT

  • Master vyšle RESET puls a čeká na PRESENCE puls. Pokud není PRESENCE, funkce končí
  • id_bit_number = 1; last_zero = 0
  • Master vyšle příkaz SEARCH (0xF0)
  • Master přečte bit ze sběrnice do proměnné id_bit, jehož hodnota bude "1 (zařízení A) AND 0 (zařízení B) AND 1 (zařízení C)" = 0
  • Master přečte další bit ze sběrnice do proměnné cmp_id_bit - jeho hodnota bude "0 (zařízení A) AND 1 (zařízení B) AND 0 (zařízení C)" = 0
  • Došlo k neshodě, protože id_bit == 0 a cmp_id_bit == 0
  • Protože id_bit_number == LastDiscrepancy, tak je search_direction nastaveno na hodnotu 1.
  • Hodnota search_direction je přidána do ROM_NO
  • Master vyšle hodnotu z search_direction (1) na sběrnici. Dalšího vyhledávání se tedy budou účastnit pouze zařízení, které mají na pozici nejnižšího bitu hodnotu 1 (zařízení A a C), zbývající (B) přejdou do čekacího módu
  • Hodnota id_bit_number je zvýšena o 1
  • Master přečte bit do id_bit, jeho hodnota bude "0 (zařízení A) AND 1 (zařízení C)" = 0
  • Master přečte doplňkový bit do cmp_id_bit, jeho hodnota bude "1 (zařízení A) AND 0 (zařízení C)" = 0
  • Došlo opět k neshodě, protože id_bit == 0 a cmp_id_bit == 0
  • Protože id_bit_number > LastDiscrepancy, tak je search_direction nastaveno na hodnotu 0, Last_Zero na hodnotu id_bit_number (tedy 2)
  • Master vyšle hodnotu z search_direction (0) na sběrnici. Zařízení, která se účastnila vyhledávání a mají na předposledním místě hodnotu 1 (tedy zařízení C) přejdou do čekacího módu
  • Bylo zjištěno druhé zařízení (zařízení A, ROM_NO == 01). Zařízení je nyní vybráno a je mu možno vyslat příkaz
  • LastDiscrepancy = LastZero (2)

NEXT

  • Master vyšle RESET puls a čeká na PRESENCE puls. Pokud není PRESENCE, funkce končí
  • id_bit_number = 1; last_zero = 0
  • Master vyšle příkaz SEARCH (0xF0)
  • Master přečte bit ze sběrnice do proměnné id_bit, jehož hodnota bude "1 (zařízení A) AND 0 (zařízení B) AND 1 (zařízení C)" = 0
  • Master přečte další bit ze sběrnice do proměnné cmp_id_bit - jeho hodnota bude "0 (zařízení A) AND 1 (zařízení B) AND 0 (zařízení C)" = 0
  • Došlo k neshodě, protože id_bit == 0 a cmp_id_bit == 0
  • Protože id_bit_number < LastDiscrepancy, tak je search_direction nastaveno na hodnotu prvního bitu z ROM_NO (1).
  • Master vyšle hodnotu z search_direction (1) na sběrnici. Zařízení B přejde do čekacího módu
  • Hodnota id_bit_number je zvýšena o 1
  • Master přečte bit do id_bit, jeho hodnota bude "0 (zařízení A) AND 1 (zařízení C)" = 0
  • Master přečte doplňkový bit do cmp_id_bit, jeho hodnota bude "1 (zařízení A) AND 0 (zařízení C)" = 0
  • Došlo opět k neshodě, protože id_bit ==0 a cmp_id_bit == 0
  • Protože id_bit_number == LastDiscrepancy, tak je search_direction nastaveno na hodnotu 1
  • Master vyšle hodnotu z search_direction (1) na sběrnici. Zařízení A přejde do čekacího módu
  • Bylo zjištěno třetí zařízení (zařízení C, ROM_NO == 11). Zařízení je nyní vybráno a je mu možno vyslat příkaz
  • LastDiscrepancy = LastZero (0), proto je nastaven příznak LastDeviceFlag

V tuto chvíli byla tedy správně rozpoznána všechna zařízení a další již na sběrnici nejsou připojena (je nastaven LastDeviceFlag).

Závěr

V článku byla popsána minimální verze algoritmu na procházení sběrnice 1-Wire™, jak jej doporučuje výrobce. V Application Note 187: 1-Wire Search Algorithm je popsána vylepšená varianta, která dokáže např. rozpoznávat pouze zařízení určitého typu. V této appnote je i vývojový diagram a zápis algoritmu v jazyce C.

Martin Malý
hw@ maly.cz

DOWNLOAD & Odkazy

Hodnocení článku: 

Komentáře

big.jedla (neověřeno) - 1. Srpen 2011 - 22:43

Ahoj, podařilo se vám někomu zprovoznit vyhledávání zařízení na síti 1wire?? Nevím teda jestli jsem to správně pochopil, ale myslím že procesor by měl nalézt všechna zařízení připojená ke sběrnici v jednom čase???
Já když mám připojena 2čidla, nalezne mi vždy pouze jedno, i když samostatně jsou nalezena obě = vyčtu jejich ID. Nemá případně někdo funkční kód pro AVR?