Maradék osztályrendszer

A maradék osztályrendszer (SOC) ( angol maradék számrendszer ) egy moduláris aritmetikán alapuló számrendszer .

Egy szám reprezentációja a maradék osztályrendszerben a maradék fogalmán és a kínai maradéktételen alapul . Az RNS-t páronkénti koprímmodulok halmaza határozza meg , vagyis úgy, hogy , amelyet bázisnak nevezünk, és egy szorzat úgy, hogy a szegmens minden egész száma egy maradék halmazhoz van társítva , ahol $(m_{1},\,m_{2},\,\dots ,\,m_{n})$ $\gcd(m_{i},\,m_{j})=1$ $(i,\,j=0,\,1,\,\pontok ,\,n;\ i\neq j)$ $M=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n},$ $x$ $[0,\M-1]$ $(x_{1},\,x_{2},\,\dots ,\,x_{n})$

x_{1}\equiv x{\pmod {m_{1))};

x_{2}\equiv x{\pmod {m_{2))};

{\megjelenítési stílus \pontok \pontok \pontok \pontok \pontok \pontok \pontok }

x_{n}\equiv x{\pmod {m_{n))}.

Ugyanakkor a kínai maradéktétel garantálja az intervallumból származó nemnegatív egészek ábrázolásának egyediségét (egyediségét) . $[0,\M-1]$

A maradék osztályrendszer előnyei

Az RNS-ben az aritmetikai műveleteket (összeadás, kivonás, szorzás, osztás) komponensenként hajtják végre, ha az eredményről tudjuk, hogy egész szám, és az is benne van . $[0,M-1]$

Összeadási képlet: hol ${\megjelenítési stílus (x_{1},x_{2},\pontok ,x_{n})+(y_{1},y_{2},\pontok ,y_{n})=(z_{1},z_ {2},\pontok ,z_{n})}$

z_{1}\equiv (x_{1}+y_{1}){\pmod {m_{1}}};

z_{2}\equiv (x_{2}+y_{2}){\pmod {m_{2}}};

{\megjelenítési stílus \pontok \pontok \pontok \pontok \pontok \pontok \pontok \pontok \pontok}

z_{n}\equiv (x_{n}+y_{n}){\pmod {m_{n))}.

A kivonás, szorzás és osztás hasonlóan történik. Megjegyzés : A felosztásra további korlátozások vonatkoznak. Az osztásnak egész számnak kell lennie, vagyis az osztónak egész számmal kell osztania az osztalékot. Az osztónak koprime-nek kell lennie a bázis összes moduljával.

A maradék osztályrendszer hátrányai

a számok összehasonlítására szolgáló hatékony algoritmusok hiánya; Általában az összehasonlítást úgy hajtják végre, hogy az RNS-ből az argumentumokat a számrendszerbe (poliadikus) fordítják, vegyes bázisokkal: ; ${\displaystyle m_{1},m_{1}m_{2},\dots ,m_{1}m_{2}\dots m_{n-1))$
lassú algoritmusok a számok ábrázolásának kölcsönös transzformációjához a helyzetszámrendszerből az RNS-be és fordítva;
összetett osztási algoritmusok (ha az eredmény nem egész);
túlcsordulás észlelésének nehézsége.

A maradék osztályrendszer alkalmazása

Az SOC-t széles körben használják a mikroelektronikában speciális DSP -eszközökben , ahol szükség van rá:

hibaelhárítás további redundáns modulok bevezetésével;
nagy sebesség, amelyet az alapvető aritmetikai műveletek párhuzamos végrehajtása biztosít;
információbiztonság .

Gyakorlati alkalmazás: Csehszlovák vákuumcsöves "EPOS" számítógép , 5E53 szovjet katonai többprocesszoros szuperszámítógép , amelyet rakétavédelmi problémák megoldására terveztek .

Speciális modulrendszerek

A moduláris aritmetikában léteznek speciális modulkészletek, amelyek lehetővé teszik a hiányosságok részleges kiegyenlítését, és amelyekhez hatékony algoritmusok vannak a számok összehasonlítására, valamint a moduláris számok közvetlen és fordított fordítására pozíciószámrendszerbe. Az egyik legnépszerűbb modulrendszer egy három páronkénti , {2 n −1, 2 n , 2 n +1} alakú koprímszám halmaza .

Példa

Vegyünk egy RNS-t bázissal . Ezen az alapon lehetőség van számok ábrázolására a -tól egy az egyhez intervallumból , mivel . A helyszámrendszerből és a maradékosztályok rendszeréből származó számok megfelelési táblázata: $(2;3;5)$ $0$ $29$ $M=2\times 3\times 5=30$

$0=(0;0;0)$	$1=(1;1;1)$	$2=(0;2;2)$	$3=(1;0;3)$	$4=(0;1;4)$
$5=(1;2;0)$	$6=(0;0;1)$	$7=(1;1;2)$	$8=(0;2;3)$	$9=(1;0;4)$
$10=(0;1;0)$	$11=(1;2;1)$	$12=(0;0;2)$	$13=(1;1;3)$	$14=(0;2;4)$
$15=(1;0;0)$	$16=(0;1;1)$	$17=(1;2;2)$	$18=(0;0;3)$	$19=(1;1;4)$
$20=(0;2;0)$	$21=(1;0;1)$	$22=(0;1;2)$	$23=(1;2;3)$	$24=(0;0;4)$
$25=(1;1;0)$	$26=(0;2;1)$	$27=(1;0;2)$	$28=(0;1;3)$	$29=(1;2;4)$

Kiegészítési példa

Adjunk hozzá két 9-es és 14-es számot a bázishoz . Ezek ábrázolása az adott alapon és (lásd a fenti táblázatot). Használjuk a képletet az összeadáshoz: $(2;3;5)$ $9=(1;0;4)$ $14=(0;2;4)$ $(z_{1},z_{2},z_{3})=(1,0,4)+(0,2,4)$

z_{1}\equiv (x_{1}+y_{1}){\pmod {m_{1}}}\equiv (1+0){\pmod {2}}=1;

z_{2}\equiv (x_{2}+y_{2}){\pmod {m_{2}}}\equiv (0+2){\pmod {3}}=2;

z_{3}\equiv (x_{3}+y_{3}){\pmod {m_{3}}}\equiv (4+4){\pmod {5}}=3;

${\megjelenítési stílus (z_{1},z_{2},z_{3})=(1,2,3)}$ - a táblázat szerint ügyelünk arra, hogy az eredmény 23 legyen.

Szorzási példa

Szorozz meg két számot 4 és 5 alapon . Ábrázolásuk az adott alapon és (lásd a fenti táblát). Használjuk a szorzás képletét: $(2;3;5)$ $4=(0;1;4)$ $5=(1;2;0)$ $(z_{1},z_{2},z_{3})=(0,1,4)*(1,2,0)$

z_{1}\equiv (x_{1}*y_{1}){\pmod {m_{1}}}\equiv (0*1){\pmod {2}}=0;

z_{2}\equiv (x_{2}*y_{2}){\pmod {m_{2}}}\equiv (1*2){\pmod {3}}=2;

z_{3}\equiv (x_{3}*y_{3}){\pmod {m_{3}}}\equiv (4*0){\pmod {5}}=0;

$(z_{1},z_{2},z_{3})=(0,2,0)$ - a táblázat szerint ügyelünk arra, hogy az eredmény 20 legyen.

Megjegyzés: ha olyan számokat szoroznánk vagy adnánk össze, amelyek a szorzás eredményeként nagyobb vagy egyenlő számot adtak, akkor a kapott eredmény, ahol a művelet eredménye a helyzeti számrendszerben. $M=30$ $RES\equiv REAL{\pmod {M}}$ $REAL$

Példa az osztásra, feltételezve, hogy egész osztás lehetséges

Az osztás a szorzással megegyező módon hajtható végre, de csak akkor, ha az osztó egyenletesen, maradék nélkül osztja az osztalékot.
Modulok esetén ossza el az 1872-es számot 9- cel. Ossza el -vel . $(29;31;32)$
$1872=(16;12;16)$ $9=(9;9;9)$

Használjuk a képletet
$z_{i}\equiv (x_{i}*y_{i}^{-1}){\pmod {m_{i}}}.$

Itt azt kell mondani, hogy ami nem ugyanaz, mint egyszerűen osztani -vel . A képlet szerint a következőket kapjuk: ${\displaystyle y_{i}^{-1}*y_{i}=1{\pmod {m_{i))))$ $x$ $y$
${\displaystyle y_{i}^{m_{i}-1}=1{\pmod {m_{i))))$
$9^{29-2}{\pmod {29}}=13,$
$9^{31-2}{\pmod {31}}=7.$
$9^{32-2}{\pmod {32}}=17;$

$z_{1}\equiv (16*13){\pmod {29}}=5,$
$z_{2}\equiv (12*7){\pmod {31}}=22,$
$z_{3}\equiv (16*17){\pmod {32}}=16.$

Ez a helyes eredmény - a 208-as szám. Ilyen eredmény azonban csak akkor érhető el, ha tudjuk, hogy az osztás maradék nélkül történik.

Lásd még

Irodalom

Akushsky I.Ya. , Juditszkij D.I. Gépi aritmetika maradék osztályokban . - Baglyok. rádió , 1968. - 439 p.
Torgasev, Valerij Antonovics. A maradék osztályok rendszere és a számítógépek megbízhatósága . - M . : Szov. rádió , 1973. - 118 p.
Amerbaev V.M. A gépi aritmetika elméleti alapjai . - A Kazah SSR Tudományos Akadémia, Matematikai és Mechanikai Intézet. Alma-Ata: Tudomány , 1976. - 324 p.
Finko O. A. Párhuzamos logikai számítások moduláris aritmetikája : Monográfia - M .: IPU RAS , 2003. - 214 p.
Évforduló Nemzetközi tudományos és műszaki konferencia "50 éves moduláris aritmetika" . - OJSC "Angstrem" , MIET . - 2005. november 23-25.; Moszkva, Zelenograd: FIZMATLIT , 2006. - 775 p. — ISBN ISBN 5-7256-0409-8 .
Amos Omondi, Benjamin Premkumar. Maradékszámrendszerek: elmélet és megvalósítás . - 57 Shelton Street Covent Garden London: Imperial College Press , 2007. - 296 p. - ISBN 978-1-86094-866-4 .
Chervyakov N. I., Evdokimov A. A., Galushkin A. I. , Lavrinenko IN et al. Mesterséges neurális hálózatok és reziduális osztályrendszerek alkalmazása a kriptográfiában . — M .: FIZMATLIT , 2012. — 280 p. - ISBN 978-5-9221-1386-1 .
Ananda Mohan, PV Residue Number Systems. - Cham: Springer International Publishing , 2016. - 351 p. - ISBN 978-3-319-41385-3 .
Amir Sabbagh, Molahosseini, Leonel Seabra de Sousa és Chip-Hong Chang (szerkesztők). Beágyazott rendszerek tervezése speciális aritmetikai és számrendszerekkel. - Cham: Springer International Publishing , 2017. március 21. - 389 p. — ISBN 978-3-319-49742-6 .

Linkek

"Moduláris aritmetika" cikk a Nagy Orosz Enciklopédiában