Systém zbytkových tříd (SOC) ( anglicky zbytek číselný systém ) je číselný systém založený na modulární aritmetice .
Reprezentace čísla v systému třídy zbytku je založena na konceptu zbytku a čínské větě o zbytku . RNS je určena sadou párových coprime modulů , to znamená tak, že se nazývá báze a součin , takže každé celé číslo ze segmentu je spojeno se sadou zbytků , kde
Čínská věta o zbytku zároveň zaručuje jednoznačnost (jedinečnost) reprezentace nezáporných celých čísel z intervalu .
V RNS se aritmetické operace (sčítání, odčítání, násobení, dělení) provádějí po komponentech, pokud je výsledek znám jako celé číslo a také leží v .
Sčítací vzorec: kde
Odčítání, násobení a dělení se provádí podobně. Poznámka : Existují další omezení dělení. Dělení musí být celé číslo, to znamená, že dělitel musí dělit dividendu celým číslem. Dělitel musí být coprime se všemi moduly báze.
SOC je široce používán v mikroelektronice ve specializovaných DSP zařízeních , kde je požadováno:
Praktické využití: Československý elektronkový počítač "EPOS" , sovětský vojenský víceprocesorový superpočítač 5E53 , určený k řešení problémů protiraketové obrany .
V modulární aritmetice existují speciální sady modulů, které umožňují částečně vyrovnat nedostatky a pro které existují účinné algoritmy pro porovnávání čísel a pro přímý a zpětný převod modulárních čísel do pozičního číselného systému. Jedním z nejpopulárnějších moduli systémů je množina tří párových prvočísel ve tvaru {2 n −1, 2 n , 2 n +1} .
Zvažte RNS se základem . V tomto základě je možné reprezentovat čísla z intervalu od do jedna ku jedné , protože . Korespondenční tabulka čísel z poziční číselné soustavy a soustavy zbytkových tříd:
Sečteme dvě čísla 9 a 14 v základu . Jejich zastoupení v daném základu a (viz tabulka výše). Pro sčítání použijeme vzorec:
- podle tabulky dbáme na to, aby výsledek byl 23.
Vynásobte dvě čísla 4 a 5 v základu . Jejich zastoupení v daném základu a (viz štítek výše). Pro násobení použijeme vzorec:
- podle tabulky dbáme na to, aby výsledek byl 20.
Poznámka: Pokud bychom měli násobit nebo sčítat čísla, která v důsledku násobení dala číslo větší nebo rovné, pak získaný výsledek, kde je výsledek operace v poziční číselné soustavě.
Dělení lze provést stejným způsobem jako násobení, ale pouze v případě, že dělitel dělí dělenec rovnoměrně, beze zbytku.
U modulů vydělte číslo 1872 9.
Vydělte .
Použijme vzorec
Zde je třeba říci, že , což není totéž jako prosté dělení podle .
Podle vzorce dostaneme:
Toto je správný výsledek - číslo 208. Takový výsledek však lze získat pouze tehdy, je-li známo, že dělení je provedeno beze zbytku.