Tesi Robotica Un coprocessore per Visual Search: Keypoint... | Page 86

4.2. SOLUZIONE ALLE PROBLEMATICHE DELL’ARCHITETTURA LUT

86

un— m—ggiore form—lizz—zione dell9—rgomentoF e t—l proposito proponi—mo —lE
™une de(nizioni e teoremi dell— teori— dei numeriF

Denizione

I sl multiEinsieme di un interv—llo ™omprendente tutti i v—lori interi

d— H — m è de(nito d—ll9insiemewm = {1, 3, 32 , 33 , ..., 3n−1 , m − (1 + 3 +

32 + 33 + ... + 3n−1 )}F

Proposizione

I ygni intero pes—to v ™on 0 ≤ L ≤ m può essere r—ppresent—to

utilizz—ndo i pesi ™ontenuti nel multiEinsieme wm F v— dimostr—zione di
quest— proposizione viene omess— per™hé non inerente —gli s™opi del nostro
do™umentoF
…n— p—rtizione di un intero positivo m è un— sequenz— ordin—t— di interi positivi
l— ™ui somm— è mX m = λ0 + λ1 + ... + λn ™on λ0 ≤ λ1 ≤ ... ≤ λn F ghi—meremo
i pesi λi le p—rti dell— p—rtizioneF

Denizione

P hiremo ™he un— p—rtizione di m è un— p—rtizione di f—™het se

IF ogni intero 0 ≤ L ≤ m può essere s™ritto ™ome L =

n
i=0

βi λi ove βi ∈

{−1, 0, 1)Y
PF non esiste —lrt— p—rtizione di m ™he soddis( il primo punto e utilizzi un
numero di p—rti inferiore — n CIY
sl primo punto può essere —n™he reinterpret—to nel seguente modoX
IF ogni intero 0 ≤ L ≤ 2m può essere s™ritto ™ome L =

n
i=0

αi λi ove αi ∈

{0, 1, 2)Y
™ostituendo un— ™osiddett— PE™omplete p—rtitionF sn ˜—se —lle proprietà di ™ui
gode questo tipo di p—rtizione possi—mo prov—re il seguente teorem—X

Teorema

I …n— p—rtizione di f—™het di un9intero positivo m e ™ostituit— preE

™is—mente d— log3 (m) + 1F