Nechť souvislý úsek nul (ukončený jedničkou nebo okrajem matice)
nalevo od A[i,j] má délku B a souvislý úsek nul nad A[i,j] má
délku C. Potom:
m[i,j] = 0, jestliže A[i,j]=0
m[i,j] = min{m[i-1,j-1], B, C} + 1, jestliže A[i,j]=1
Hodnoty B a C můžeme pro všechny prvky matice A snadno spočítat
a uložit do pomocných matic při jediném průchodu v čase O(n2).
Potom již můžeme postupně počítat všechny hodnoty m[i,j].
Budeme-li postupovat například po řádcích shora dolů, budeme mít
při výpočtu m[i,j] už k dispozici hodnotu m[i-1,j-1]. Stačí tedy
na základě známých hodnot m[i-1,j-1], B, C a A[i,j] v konstantním
čase určit hodnotu m[i,j]. Celková časová složitost algoritmu je
tudíž O(n2).
Právě popsané řešení úlohy nyní ještě vylepšíme z hlediska paměťové náročnosti. Hodnoty B a C totiž není třeba počítat předem pro všechny prvky matice A a ukládat je do pomocných matic. Hodnotu B si můžeme vždy průběžně počítat při průchodu řádkem matice zleva doprava a udržovat si ji v jedné pomocné proměnné (tato hodnota vůbec nezávisí na ostatních řádcích matice). Hodnoty C se snadno počítají na základě hodnot C v předchozím řádku, stačí nám tedy použít pomocné jednořádkové pole. Hodnoty m[i,j] si budeme ukládat přímo do matice A.
Nechť zpráva má n=2k-1 bitů označených b1..bn (v případě, že je kratší, považujeme zbylé bity za nuly). My ji doplníme o paritní bit p (stejně jako v ukázkovém příkladu v zadání) a zabezpečovacími bity c0 až ck-1, jež budou paritními bity jednotlivých bloků zvolených podle následujícího pravidla: v i-tém bloku budou právě ty bity, jejichž pořadové číslo (pro bit bz to je z) má v i-tém binárním řádu jedničku (každý bit původní zprávy tak patří do alespoň jednoho bloku a je jednoznačně identifikován tím, do kterých bloků patří a do kterých nikoliv).
P-III-3 Kombinační sítě
Nechť A= {0,1,2,3,4,5,6,7,8,9,@} je abeceda naší
sítě. Pak pro všechny symboly s, prvky A, označíme C <= s
počet vstupů Ai, na nichž je hodnota menší nebo rovná s
(jelikož
C <= s <= n, lze všechna C <= s vyjádřit ve dvojkové
soustavě nějakými bity C <= s,1 ... m, kde m=[log2 n]).
Výstup Bi pak bude mít hodnotu s právě tehdy, je-li
s největší prvek abecedy, pro nějž platí C <= s <= i. Jinými
slovy: setříděná posloupnost vypadá tak, že nejdříve obsahuje C <=
0 nul, pak až do pozice C <= 1 jedničky ... až do pozice
C <= 9=n devítky.
Pro realizaci tohoto algoritmu kombinační sítí budeme využívat následující
podsítě:
TEST
<= (s,x) -
hradlo mající na výstupu 1, pokud x <= s, jinak 0.ADD
t(X1... t,
Y1... t) = Z1... t - sčítačky sčítající
t-bitová binární čísla X a Y s výsledkem Z (odvozeno v oblastním
kole s hloubkou O(log t)).CMP
t(A1... t, B1... t) = R - komparátory porovnávající dvě t-bitová
binární čísla a dávající výsledek R=0 pro A=B, R=1 pro A < B a R=2
pro A > B. Odvodíme známým způsobem:
CMP
1(0,0) = CMP
1(1,1) = 0,
CMP
1(0,1) = 1,
CMP
1(1,0) = 2.
Tento předpis přímo definuje hradlo CMP
1.CMP
tp(AH,BH) a
CL=CMP
tp(AL,BL)
a pokud CH <> 0, použijeme jako výsledek CH,
jinak je výsledkem
CL (pro tuto funkci opět definujeme hradlo).STEP
s(a,x) (s prvkem A) -
hradla s následující přechodovou funkcí:
STEP
s(a,x) = s, pokud x <> 1.STEP
s(a,1) = a.FIRST
(x0, ..., x9) -
výstupem je nejmenší s takové, že xs <> 1.
Konstruujeme z hradel STEP
s:
FIRST
(x9) = 9FIRST
(xs,...,x9) =
STEP
s
(FIRST
(xs+1,...,x9),xs).FIRST
je 9.TEST
<= (s,Xi)
mající hodnotu
1 právě tehdy, je-li Xi <= s,
jinak 0 (to zvládneme sítí hloubky 1).
Rozšíříme-li každou z těchto proměnných
nulami na m-bitové číslo X <= s,i,1 ... m,
je zjevně C <= s součtem
čísel X <= s,i přes všechna i.
Pro určení tohoto součtu stačí využít asociativity
sčítání a nejdříve sečíst všechny
dvojice X <= s,2k + X <= s,2k+1, pak dvojice
těchto dvojic atd. (viz hledání minima a maxima
v domácím kole, kde se používá tentýž
trik), čimž získáme konečný součet C <= s
sítí o m úrovních, z nichž
každá se skládá z m-bitových sčítaček
(ADD
m) hloubky O(log m), tedy
celková hloubka sítě určující C <= s
je O(m log m)=O(log n loglog n).
Poté spočteme pro každou výstupní pozici i a každý symbol abecedy s hodnoty
Zs,i = CMP
m(C <= s, i)
(hloubka O(log m))
a definujeme
Bi = FIRST
(Z0,i, ..., Z9,i)
jako výstupy sítě
(hloubka O(1)). Tedy Bi je nejmenší
s takové, že CMP
m(C <= s,i) <> 1, tudíž
nejmenší takové, pro nějž C <= s >= i, což je přesně
hodnota odvozená v prvním
odstavci.
Síť se skládá ze čtyř částí hloubek po řadě O(1), O(log n loglog n), O(loglog n) a O(1), její celková hloubka proto je O(log n loglog n).