D é n e s T a m á s matematikus
e-mail: tdenest@freemail.hu
Latin négyzetek alkalmazásai
a kísérlet tervezésben és kódolásban
A latin négyzetek gyakorlati alkalmazásai főleg három területre irányulnak:
a.) statisztikus kísérlet tervezés
b.) kódolás (hírközlés)
c.) titkosítás
Míg a statisztikai alkalmazásokban R.A. Fisher tekinthető úttörőnek, az 1920-as években megkezdett tevékenységével és híres könyvével (The design of experiments), addig a latin négyzetek hírközlésben való alkalmazása a II. világháborút megelőzően, illetve alatta kezdődött úgy amerikai, mind német részről. Az első publikált eredmények azonban, érthető okokból, csak a háború befejezése után jelentek meg. Amerikai részről C. E. Shannon, német részról Rudolf Schauffler (a német rejtjelfejtés kimagasló alakja a II. világháború alatt) nevét kell megemlíteni úttörőként.
Alkalmazások a statisztikus kísérlet tervezésben
R.A. Fisher volt az első aki rámutatott, hogy az addigi gyakorlattal szemben – amikor a kísérletek során egyetlen tényezőt változtattak – célszerű az összes tényező (az úgynevezett faktorok) egyidejű variálása. Így jött létre a statisztika egy új ága, a faktor-analízis, valamint a latin négyzetek kísérletek tervezésében való felhasználása.
Az ortogonális latin négyzetek statisztikai alkalmazását egy példán keresztül szemléltetem. Öt különféle kikészítésű szálból szőtt késztermék mintázatát kell minőségileg összehasonlítani. A késztermék előállításán öt szövőgépen öt gépkezelő dolgozik. Az a feltételezés (amit igazolni kell), hogy a szálak kikészítésén kívül a szövéshez felhasznált gép és kezelője is a minőséget befolyásoló tényezők. Ha a kísérletekre szánt idő nem lenne korlátozó tényező, akkor minden egyes fonalfajtát mind az öt szövőgépen az öt gépkezelő mindegyikével ki kellene próbálni. Ez összesen 125 kísérletet jelent. A latin négyzetek segítségével azonban kielégítő eredményt lehet elérni 25 kísérletből álló kísérlet sorozattal. Tegyük fel, hogy K1, K2,…, K5 jelöli az öt gépkezelőt és S1, S2,…, S5 jelöli az öt szövőgépet, valamint Y1, Y2,…,Y5 az öt különféle szál jelölésére szolgál.
A minőség összevetésére szolgáló 25 kísérletet az 1/a.ábrán bemutatott latin négyzet szemlélteti.
|
|
K1 |
K2 |
K3 |
K4 |
K5 |
|
S1 |
Y1 |
Y4 |
Y5 |
Y2 |
Y3 |
|
S2 |
Y3 |
Y1 |
Y2 |
Y4 |
Y5 |
|
S3 |
Y2 |
Y5 |
Y1 |
Y3 |
Y4 |
|
S4 |
Y5 |
Y3 |
Y4 |
Y1 |
Y2 |
|
S5 |
Y4 |
Y2 |
Y3 |
Y5 |
Y1 |
|
1 |
4 |
5 |
2 |
3 |
|
3 |
1 |
2 |
4 |
5 |
|
2 |
5 |
1 |
3 |
4 |
|
5 |
3 |
4 |
1 |
2 |
|
4 |
2 |
3 |
5 |
1 |
1/a. ábra
1/b. ábra
Az 1/a. ábrán látható latin négyzet úgy alkalmazható a kísérletek tervezésénél, hogy az oszlop kiválasztással a kezelőt, a sor kiválasztással a szövőgépet és a kiválasztott sor és oszlop metszetében álló elemmel az adott kísérletben felhasznált fonalat határozzuk meg. Így például az első kísérlet: a K1 gépkezelő az S1 szövőgépen Y1 fonallal dolgozik.
Tegyük fel továbbá, hogy a gépkezelők hatékonyságát befolyásolja, hogy a hét mely munkanapján dolgoznak. Akkor az 1/a. ábrán megadott latin négyzetben szereplő indexekhez (lásd 1/b. ábra) tartozó ortogonális párt kell szerkeszteni (lásd 2/a. ábra), ahol a munkanapokat számok jelzik. ( 1 = hétfő, 2 = kedd, 3 = szerda, 4 = csütörtök, 5 = péntek.)
|
1 |
2 |
3 |
4 |
5 |
||
|
3 |
4 |
1 |
5 |
2 |
||
|
2 |
3 |
5 |
4 |
1 |
||
|
5 |
1 |
3 |
2 |
4 |
||
|
4 |
5 |
2 |
1 |
3 |
||
|
|
K1 |
K2 |
K3 |
K4 |
K5 |
|
|
S1 |
1,1 |
4,2 |
5,3 |
2,4 |
3,5 |
|
|
S2 |
3,3 |
1,4 |
2,1 |
4,5 |
5,2 |
|
|
S3 |
2,2 |
5,3 |
1,5 |
3,4 |
4,1 |
|
|
S4 |
5,5 |
3,1 |
4,3 |
1,2 |
2,4 |
|
|
S5 |
4,4 |
2,5 |
3,2 |
5,1 |
1,3 |
|
2/a. ábra
2/b. ábra
A két ortogonális latin
négyzet (lásd az 1/b. és 2/a. ábrán) egymásra helyezésével megszerkesztett 25
kísérletből álló kísérletsorozatot ábrázolja a 2/b. ábra, amely lehetővé teszi,
hogy minden egyes gépkezelő minden egyes szövőgépen dolgozzon, a munkájában az
öt különböző kikészítésű fonal mindegyikét pontosan egyszer használja és a vele
kapcsolatos kísérleteknél egy hét 5 munkanapja közül minden napra egy kísérlet
jusson. Hasonló típusú kísérletek megtervezése merül fel például a
növénytermesztés, vagy a gyógyszer kutatás területén is.
Nyilvánvaló, hogy a
kísérlet tervezésénél a latin négyzetek alkalmazhatósága bizonyos szempontból korlátozott,
hiszen ha az előbbi példánkban például a gépkezelők száma nem öt, hanem négy,
akkor már másfajta elrendezésre van szükség. Az ilyen, a latin négyzeteknél
általánosabb elrendezéseket block designoknak nevezzük. Az érdeklődő
olvasó jó betekintést kaphat a block designokról [6]-ből.
Egy másik példa világítja
meg a teljes latin négyzetek alkalmazását a kísérletek tervezésében:
Egy állatkísérletben a
kísérleti állatokat különböző étrend szerint táplálják, feltevés szerint (amit
a kísérletek során ellenőrizni kívánnak) egy adott állat etetése előtt, a
kísérlet során kapott összes étkezések száma, valamint a közvetlenül megelőző
etetés során kapott takarmány fajtája befolyásolja az eredményt.
Tegyük fel, hogy n
darab állat és n féle takarmány kerül a kísérletben felhasználásra. n=4
esetén az A1 , A2 , A3 , A4 kísérleti
állatot a T1 , T2 , T3 , T4 takarmányokkal
táplálják a 3. ábrán látható teljes latin négyzet szerinti kísérleti
elrendezésben.
|
|
1 |
2 |
3 |
4 |
|
A1 |
T1 |
T2 |
T3 |
T4 |
|
A2 |
T2 |
T4 |
T1 |
T3 |
|
A3 |
T3 |
T1 |
T4 |
T2 |
|
A4 |
T4 |
T3 |
T2 |
T1 |
3. ábra
A 3. ábrán látható
kísérleti elrendezés azt jelenti, hogy például az A1 állatnak
első étkezésre T1 takarmányt, másodikra T2
takarmányt stb. kell adni. A kísérlet sorozatban valóban fontos a teljes latin
négyzet tulajdonság (ennek definíciója e cikk I. részében található), hiszen ez
biztosítja, hogy az összes lehetséges takarmány sorrendet kipróbáljuk, ami
éppen a kísérlet egyik lényeges célját képezi.
Kódolás elméleti alkalmazások
Érdekes megemlíteni, hogy az általánosan elterjedt nézetekkel szemben, nem Richard Wesley Hamming volt az első aki 1950-ben a hiba jelző és javító kódokat bevezette (lásd az alábbi képet), hanem Rudolf Schauffler akinek latin négyzetek alapján szerkesztett nem bináris hibajelző és javító kódjai, valamint a latin négyzetek egyéb alkalmazásai már az 1946-ban benyújtott doktori disszertációjában szerepeltek.
Mivel R. Schauffler eredményei a titkos szolgálatnál töltött évei és a szigorú titoktartás következtében, szélesebb körben hozzáférhető módon csak l956-ban jelentek meg, így Hamming bináris hibajelző és javító kódjait független eredménynek kell tekinteni. Schauffler gondolatait jóval később viszontláthatjuk [1]-ben és [5]-ben.
A latin négyzeteken alapuló nem bináris hibajelző és javító kódok elterjedéséhez a feltételt azonban a szélessávú űrtávközlési csatornák megjelenése teremtette meg. Ezért S.W. Golomb és E.C. Posner a JPL (Jet Propulation Laboratory) pasadénai kutató laboratórium vezető munkatársaiként foglalkoztak a hiba jelző és javító kódok latin négyzetek alapján való szerkesztésével. Eredményüket a következőkben lehet megfogalmazni:
Ha létezik t darab n-ed rendű latin négyzetből álló ortogonális rendszer, akkor létezik olyan t+2 hosszúságú kódszavakból álló kód, amelynek minimális Hamming távolsága t+1 és amelyben n2 kódszó van.
Két k hosszúságú kódszó a=(a1, a2,……..ak) és b=(b1, b2 …..bk) közötti Hamming távolság (jele=d(a,b)), azon i (i=1,2,…..k) indexeknek a száma amelyekre ai ¹ bi teljesül.
Egy kódnak a minimális Hamming távolsága a kódban szereplő összes kódszó párok közötti Hamming távolságok minimuma.
Alapvető tételként kell e helyen megemlíteni, hogy egy q betűből álló ábécé feletti k hosszúságú d minimális Hamming távolságú kódban maximum qk-d+1 kódszó lehet.
Így a fent leírt Golomb-Posner kódban a kódszavak száma nt+2–(t+1)+1 =n2, ami n-ed rendű latin négyzetek esetén maximális.
A Golomb-Posner kód konstrukciója a következő példán jól követhető:
Legyen n=4, a konstrukcióhoz az L1, L2, L3 páronként ortogonális negyed rendű latin négyzeteket használjuk fel (lásd 4. ábra).
4. ábra
Látható módon L1-hez a keret elemeket is feltüntettük, mivel ennek a kódszavak képzése során jelentősége lesz. A kódszavakat a következő módon képezzük:
az első komponens a sorkeret elem ai (i=1,2,3,4), a második komponens az oszlopkeret elem bj (j=1,2,3,4), majd sorrendben ezen keret elemek után következnek az L1, L2, L3 latin négyzetek belsejében ai sor bj oszlop metszésénél lévő elemek. Így a 4. ábra L1, L2, L3 latin négyzeteiből az 5. ábrán lévő kódszó készlethez jutunk. Az olvasó ellenőrizheti, hogy a kódszavak száma 42 = 16, a szóhossz 5, a minimális Hamming távolság 4.
(0 0 0 0
0) (1 0
1 2 3) (2 0
2 3 1) (3 0
3 1 2)
(0 1 1 1
1) (1 1
0 3 2) (2 1
3 2 0) (3 1
2 0 3)
(0 2 2 2
2) (1 2
3 0 1) (2 2
0 1 3) (3 2
1 3 0)
(0 3 3 3
3) (1 3
2 1 0) (2 3
1 0 2) (3 3
0 2 1)
5. ábra
Az I. részben említett
tized rendű latin négyzetekből álló ortogonális rendszer létrehozásának
problémája (létezik-e három 10-ed rendű latin négyzetből álló ortogonális
rendszer?) most a kódok nyelvére lefordítva így hangzik: van-e olyan
Golomb-Posner kód amelyben a 10 elemű ábécé feletti kódszavak száma 100,
hosszuk 5 és a kód minimális Hamming távolsága 4?
A Golomb-Posner kódok előnye, hogy n ¹ 2, illetve n ¹ 6 esetén tetszőleges n elemű ábécé felett léteznek. [2]-ben sikerült a Golomb-Posner féle konstrukciót ortogonális latin téglalapokra általánosítani
A latin téglalap olyan téglalap mátrix, amely kiegészíthető latin négyzetté. Két azonos méretű latin téglalapot akkor nevezünk ortogonálisnak, ha egymásra helyezve a megfelelő rendezett párok mind különbözőek.
Példát mutatunk be a párok [2]-ban közölt konstrukciója alapján arra, hogy az R1, R2, R3, R4, R5 2x6 méretű latin téglalapokból álló ortogonális rendszerből (lásd 6. ábra) milyen kód nyerhető.
6. ábra
A konstrukció követhetősége érdekében R1-nél a perem elemeket is feltüntettük. A konstrukció a latin négyzetekre alkalmazott Golomb-Posner eljárásnak értelemszerű analogonja. Az így kapott kód elemeit (kódszavait) a 7. ábrán láthatjuk.
|
(1166666) |
|
(1212345) |
|
(2111111) |
|
(2223456) |
|
(3122222) |
|
(3234561) |
|
(4133333) |
|
(4245612) |
|
(5144444) |
|
(5256123) |
|
(6155555) |
|
(6261234) |
7. ábra
A fenti
konstrukció felhasználható személyi számok, jogosítvány, vagy ISBN számok,
valamint más hasonló kódok
előállítására. Az ortogonális rendszer miatt a keletkező kódszavak garantáltan
különbözőek, az eljárás könnyen programozható, gyors előállítást kínál.
Alkalmazások a távközlésben
Egy mobil telefon hálózati rendszerben egy nagyobb területet felosztanak kisebb területi egységekre és minden egységnek van egy telepített adó-vevő központja. Ez a központ a környezetében dolgozó adók üzenetét veszi és továbbítja egy másik központ felé. Természetesen a területi központ a más körzetből érkező üzeneteket veszi és a saját területi egységén belül osztja szét, így nagyszámú frekvencia felhasználása szükséges egy ilyen rendszer üzemeltetéséhez. A felhasználható frekvenciák száma viszont korlátozott, valamint áthallási okok miatt az azonos frekvenciák egymáshoz közel fekvő adóknál nem alkalmazhatók. Ezért olyan célszerű frekvencia kiosztást kell javasolni, amely a frekvenciák ismételt felhasználásával csökkenti a szükséges frekvenciák számát és a „lóugrásos” latin négyzeteken alapuló frekvencia kiosztással megakadályozza az áthallást, illetve a zavarást. A megoldást e cikk I. részében említett Nasik négyzet alkalmazása biztosítja.
A 10. ábrán bemutatott Nasik négyzet (ez egy olyan Nasik négyzet amely egyben latin négyzet is és rendelkezik a lóugrás tulajdonsággal) olyan tulajdonságú, hogy minden egyes eleme (egy elem egy frekvencia kiosztást reprezentál) nyolc olyan elemmel szomszédos, amelyek közül két szomszédos elemhez nem rendelhető azonos frekvencia. A 10. ábrán bemutatott latin négyzet ötödrendű, ez azt jelenti, hogy a javasolt eljárás használatához legalább öt különböző frekvencia szükséges. Természetesen az egy adó-vevőhöz rendelt frekvenciák száma egynél jóval több is lehet.
|
0 1
2 3 4 |
|
2 3
4 0 1 |
|
4 0
1 2 3 |
|
1 2
3 4 0 |
|
3 4
0 1 2 |
|
10.ábra |
Egy frekvencia ugratásos hírközlő rendszer úgy jellemezhető, hogy n frekvenciát használhat a rendszerben működő legfeljebb n adó. Az adók mindegyike bizonyos időközönként frekvenciát vált a zavarás megnehezítése végett vagy egyéb okokból. A frekvencia ugratásos hírközlő rendszer akkor hatékony, ha a rendszerben működő adók egymástól függetlenül (külső szinkronizálás nélkül) működhetnek azonos frekvenciákat használhatnak oly módon, hogy az ütközés (két adónak egy időben azonos frekvencia használata) elkerülhető legyen. R. D. Yates és G. R. Cooper már 1966-ban készített kutatási jelentésükben javasolták latin négyzetek alkalmazását a frekvencia ugratás hatékonyságának növelésére.
Alkalmazás a digitális kép
kódolás és átvitel területén
Egy (0,1) mátrixról akkor mondjuk, hogy uxv (u,v³2) horizontális ablak tulajdonsággal rendelkezik, ha egy u sorból és v oszlopból álló ablakot horizontálisan mozgatva a mátrixon, minden nem csupa nullából álló ablak legfeljebb egyszer fordul elő. (Hasonlóképpen definiáljuk a vertikális ablak tulajdonságot.)
Egy mátrixot akkor mondunk uxv ablak tulajdonságúnak, ha horizontálisan és vertikálisan is uxv ablak tulajdonságú.
Természetes általánosítása a fogalomnak, ha egy latin négyzettől követeljük meg a horizontális, illetve vertikális ablak tulajdonságot. (0,1) mátrixokra az ablak tulajdonságot két Bell laboratóriumban dolgozó matematikus (F.J. MacWilliams, N.J.A. Sloane vizsgálták először. Az ablak tulajdonsággal rendelkező mátrixok szerkesztése gyakorlati alkalmazásokkal is bír, például a digitális kép kódolás és átvitel területén.
Most bemutatunk egy példán keresztül ablak tulajdonságokkal rendelkező mátrix szerkesztést, amely mint látni fogjuk a teljes latin négyzeteken alapul.
Tekintsünk egy negyedrendű teljes L4(aij) latin négyzetet (lásd 11.ábra), majd utolsó oszlopát megismételve, valamint egy kizárólag ötösöket tartalmazó oszlopot hozzávéve kapjuk a 12. ábrán látható M4x6(bij) mátrixot.
11. ábra
12. ábra
A teljes latin négyzet
tulajdonságból következik, hogy úgy a 11.ábra L4(aij)
latin négyzete, mint a 12.ábra M4x6(bij)
kiterjesztése rendelkezik a vertikális, illetve horizontális 2x2 ablak
tulajdonsággal.
Vesszőmentesnek nevezünk egy C kódot, amely n hosszúságú
szavakból áll, ha bármely 
és 
esetén az 
(j=2,3,...,n)
kódszavak egyike sincsen C-ben.
Szemléltető példaként a
12.ábra mátrixát és a 13.ábra bináris vesszőmentes kódját felhasználva, az 
(i=1,2,3,4 j=1,2,3,4,5,6) megfeleltetéssel nyerjük
a 14.ábrán látható (0,1) mátrixot, amely 14x1 ablak tulajdonságú.
13. ábra
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
2 |
|
|
|
|
3 |
|
|
|
|
4 |
|
|
|
|
5 |
|
|
|
|
6 |
|
|
|
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
|
i |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
|
3 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
|
|
4 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
14. ábra
A fenti latin négyzeteket
felhasználó szerkesztési mód részletes leírása megtalálható [3]-ban.
Latin négyzet alapú párhuzamos aritmetika
A számítástechnika egyik
legégetőbb problémája a műveletvégzési idők lerövidítése. Ennek érdekében
jöttek létre a különböző párhuzamos műveletet végző architektúrák (pipeline
processzorok, array processzorok stb.)
Nem kaptak eddig megfelelő szerepet az úgynevezett maradék számrendszerbeli ábrázoláson alapuló aritmetikai egységek. Ilyen aritmetikai egység ismertetésére és a latin négyzetekkel való kapcsolatára derül fény a következőkben. Ezen példa kapcsán rámutatunk a latin négyzetek művelet táblaként való kódolási alkalmazására.
A számok maradék számrendszerbeli ábrázolásának kezdetei az ókori Kínában keletkezett, úgynevezett kínai maradéktételen alapszik. Mivel e tétel több mint kétezer éves, nem természetes, hogy a soros műveletvégzés lett a számítástechnika születésénél az első és napjainkig is alapvetően elterjedt architektúra. Néhány olyan tudomány és technikatörténeti tényt igyekeztem [4] könyvemben közkincsé tenni, amelyek ezt a jelenséget még érdekesebbé teszik. Eme kevéssé ismert tények szerint már a XX. század első felében történt kísérlet a maradék számrendszerbeli ábrázoláson alapuló célgép (prímszám szita) készítésére, később D.N. Lehmer, majd fia D.H. Lehmer hasonló célú és megoldású fotoelektronikus gépet épített. D.H. Lehmer aki ott volt az ENIAC születésénél, annak soros architektúrájúvá tételéről a következőket írta:
„A következő dátumunk 1946, ami természetesen az ENIAC
éve. Vajon felhasználható-e a nagysebességű számítógép a szita-módszer
elvégzésére? Ez egy magas párhuzamosságú gép volt, amíg von Neumann el nem
rontotta.”
A kínai maradék tétel:
Pontosan egy olyan x< n természetes szám van amelyre fennállnak a következő kongruenciák, xºa1 mod m1, xºa2 mod m2 ,…., xºak mod mk, ha m1,m2, …, mk páronként relatív prímek és n = m1·m2·…·mk
(Az x º ai mod mi írásmód azt jelenti, hogy az x számot mi-vel osztva ai maradékot ad). Azt mondjuk, hogy az x szám maradék számrendszerbeli ábrázolása az (a1a2….ak) vektor.
Az összeadás, kivonás, szorzás a maradék számrendszerben ábrázolt számok között komponensenként történik. Legyen x maradék számrendszerbeli ábrázolása (a1a2….ak) és y ábrázolása (b1b2….bk) akkor x+y ábrázolása (a1Åb1a2Åb2…akÅbk), ahol a Å művelet a mod ni (i = 1,2,..,k) összeadást jelenti. Hasonló módon értelmezhető a kivonás és a szorzás is.
A 15.ábra táblázata bemutatja a 0-15 közé
eső egész számok 3 és 5 modulusra vonatkozó maradék számrendszerbeli alakjait,
majd egy példán keresztül érzékeltetem a maradék számrendszerben való
összeadást. Eme táblázat segítségével már képes bárki ebbe a szám intervallumba
eső számokkal műveleteket végezni, ezáltal megtapasztalni azt a meghökkentő
lehetőséget, amit a párhuzamos számítás (párhuzamos aritmetika) jelent.
|
Egész számok |
m1 3 |
m2 5 |
|
0 |
0 |
0 |
|
1 |
1 |
1 |
|
2 |
2 |
2 |
|
3 |
0 |
3 |
|
4 |
1 |
4 |
|
5 |
2 |
0 |
|
6 |
0 |
1 |
|
7 |
1 |
2 |
|
8 |
2 |
3 |
|
9 |
0 |
4 |
|
10 |
1 |
0 |
|
11 |
2 |
1 |
|
12 |
0 |
2 |
|
13 |
1 |
3 |
|
14 |
2 |
4 |
|
15 |
0 |
0 |
15. ábra
Táblázat a 0-29 természetes számok maradék számrendszerbeli
ábrázolására.
A maradék számrendszerben az összeadás, vagy a kivonás
sokkal gyorsabban, valóban az összes
számjegyen szinte egyszerre (párhuzamosan) elvégezhető, mivel nincs átvitel.
Illusztrációként a 16.ábrán bemutatjuk a következő műveletek elvégzését modulus
rendszerben: 7+3+1=11
|
Össze- Adandók |
m1 3 |
m2 5 |
|
7 |
1 |
2 |
|
3 |
0 |
3 |
|
1 |
1 |
1 |
|
Eredmény: |
2 |
1 |
16. ábra
Az összeadás eredménye (2,1) a 15.táblázat 11.
sorában megtalálható, vagyis a modulus alakban kapott eredmény valóban a tízes
számrendszerben kiszámított 11-nek felel meg.
A kínai maradék tétel tehát ad egy olyan szám ábrázolási módot, amelynek segítségével a párhuzamos műveletvégzés könnyen megvalósítható.
A modulus aritmetika
műveleteihez tartozó művelet táblák egy-egy latin négyzetet alkotnak. A fent
bemutatott mod 3, illetve mod 5
összeadáshoz tartozó művelet táblákat mutatják a 17.ábrán látható
peremezett latin négyzetek:
|
Å3 |
0 |
1 |
2 |
|
0 |
0 |
1 |
2 |
|
1 |
1 |
2 |
0 |
|
2 |
2 |
0 |
1 |
|
Å5 |
0 |
1 |
2 |
3 |
4 |
|
0 |
0 |
1 |
2 |
3 |
4 |
|
1 |
1 |
2 |
3 |
4 |
0 |
|
2 |
2 |
3 |
4 |
0 |
1 |
|
3 |
3 |
4 |
0 |
1 |
2 |
|
4 |
4 |
0 |
1 |
2 |
3 |
17. ábra
Most példát adunk a mod 3 és mod 5 modulus aritmetikabeli szorzásra, illetve a szorzás elvégzéséhez szükséges művelettáblákra, amelyek a perem sor, illetve oszlop elhagyásával latin négyzetet alkotnak (lásd 18.ábra).
|
|
0 |
1 |
2 |
3 |
4 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
2 |
3 |
4 |
|
2 |
0 |
2 |
4 |
1 |
3 |
|
3 |
0 |
3 |
1 |
4 |
2 |
|
4 |
0 |
4 |
3 |
2 |
1 |
5
|
|
0 |
1 |
2 |
|
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
2 |
|
2 |
0 |
2 |
1 |
3
18. ábra
Az összeadásnál bemutatott
15.táblázat szerint: 3=(0,3), 5=(2,0), ekkor 3·5=(0
32, 3
50)= (0,0), amely a táblázat 15. sorában
található, tehát a szorzás eredménye 15, ami megfelel a tízes
számrendszerbelinek.
A bemutatott példákból is kiderül, hogy a modulus aritmetika használatának fő nehézségét a túlcsordulás, valamint az előjel jelzése és a maradék számrendszerbeli ábrázolásból a tízes számrendszerbe és viszont konvertálás viszonylagos lassúsága jelenti. Ezt az ábrázolás módot tehát ott célszerű alkalmazni, ahol a számolás igény nagy és csak ritkán kell konvertálni a számokat. Ugyanakkor a párhuzamos műveletvégzés mellett a maradék számrendszeren alapuló aritmetikai egység nagy előnye a művelettáblák (latin négyzetek) ROM-okban való egyszerű tárolhatósága.
Hivatkozás jegyzék
[1] A..M. Andrew: Decimal error-correction: a
solution
Computer J. 18
(1975) 284-285
[2] J.Dénes Latin squares and non-binary encoding
Proc.Conf.Information Theory (Cachen, France, 1977), CNRS, Paris 1979. 215-221
[3] J.Dénes, A.D. Keedwell: A new construction of twodimensional araye with
window property.
IEEE Trans. On Information Theory 1988.
[4] Dénes Tamás: Titkos-számítógép-történet
Aranykönyv Kiadó, Budapest, 2003.
[5] A.Ecker and G. Poch: Check character systems
Computing 37(1986), 289-297
[6] D.R.Hughes, F.C. Piper: Design theory
Cambridge University Press,
London, New York, New Rochelle, Melbourne, Sydney, 1985
[7] D.H.Lehmer: A photo-electric number sieve
Amer.Math.Monthly 40 (1933) 401-406
[8] D.H.Lehmer: A machine for combining sets of linear conqruences.
Mathematische Annalen 109 (1934) 661-667
[9] R. Mandl: Orthogonal latin squares: an application of experimental design
to compiler testing. Comm
ACM 28(1985) 1054-1058