US 2004/0170273 A1Published application

Coding method, particularly a numeric coding method

OwnerLuigi Carabiniere, Pierluigi Mirto +1inventors

InventorsLuigi Carabiniere, Pierluigi Mirto, Giancarlo Formicuccia

Life of this patent

Estimating the term…

Loading patent…

Abstract

An apparatus and method for encoding an input string A into an output string B, whose items an and bn belong to an alphabet S of M symbols sm, the method being characterised by providing an ordered arrangement of the M symbols sm of the alphabet S, by performing a scanning operation on the items an of the input string A and in that, for each of the items ak, where k ε{0, 1, . . . , N−1}, it includes arranging in decreasing order in an ordered arrangement vector O (whose items oj include the indexes i of items ƒi) the M items ƒi of an occurrence vector F of the symbols sm of the alphabet S in at least a portion Wk⊂A of Tk items, establishing a permutation vector P consisting of M items pt, whose items are such as to fulfil the following relationship poj=j and assigning to item bk of the output string B the symbol bk=SE(hPt=w) where w is the w-th index hw of the ordered succession H such as to fulfil the relationship ak=Shw and the enciphering function E(m) is an invertible function whose dominion and co-dominion are coinciding.

Claims47

Dependent claims

A method for encoding an input string A into an output string B, both the input string A and the output string B comprising N items, respectively, an and bn, where n=0, 1, . . . , N−1, with items an and bn belonging to an alphabet S of M symbols sm, where m=0, 1, . . . , M−1, the method comprising the steps of:

A. providing an ordered arrangement of the M symbols sm of the alphabet S as represented by a corresponding ordered succession H={hl, where l=1, . . . , M−1} of the indexes m, such that
hlε{0, 1, . . . , M−1}hq≠hr for q≠r,
in that a scanning operation is carried out on items an of the input string A and in that, for each of the items ak, where k ε{0, 1, . . . , N−1}, it includes the following steps:
B. arranging in decreasing order the M items ƒi, where i=0, 1, . . . , M−1, of an occurrence vector F of the symbols sm of the alphabet S in at least a portion Wk⊂A of Tk items an of the input string A, where Tk≧0, each item ƒi being equal to the number of occurrences in portion Wk of the corresponding symbol shi, in respect of which the following relationship is fulfilled:
5 ∑ i = 0 M - 1 ⁢ f i = T k ,
the items ƒi of the occurrence vector F being arranged in an ordered arrangement vector O comprising M items oj, where j=0, 1, . . . , M−1, whose items oj include the indexes i of items ƒi of vector F arranged in decreasing order, by employing, when two items ƒi are equal, the arrangement of the symbols sm of the alphabet S, as represented by the corresponding ordered arrangement H, such that
ƒox≧ƒoy, ∀y>x
and
for ƒoz=ƒoz+1, oz=u<v=oz+1,
where
H={h0, . . . , hu, . . . , hv, . . . , hM−1}
C. establishing a permutation vector P consisting of M items pt, where t=0, 1, . . . , M−1, whose items are such as to fulfil the following relationship
poj=j for j=0, 1, . . . , M−1
and
D. assigning to item bk of the output string B the symbol
bk=sE(hpt=w)
where w is the w-th index hw of the ordered succession H such as to fulfil the relationship
ak=shw
and the enciphering function E(m) is an invertible function whose dominion and co-dominion are coinciding and are equal to the assembly {0, 1, . . . , M−1}:
6 { g = E ⁡ ( m ) ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } m = D ⁡ ( g ) = E - 1 ⁡ ( g ) ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } .

17 more elements

A method for decoding an input string B into an output string A, both the input string B and the output string A comprising N items, respectively, bn and an, where n=0, 1, . . . , N−1, with items bn and an belonging to an alphabet S of M symbols sm, where m=0, 1, . . . , M−1, the method comprising the steps of:

A. providing an ordered arrangement of the M symbols sm of alphabet S represented by a corresponding ordered succession H={hl, where l=0, 1, . . . , M−1} of the indexes m, such that
hlε{0,1, . . . , M−1}hq≠hr, for q≠r,
in that a scanning operation of items bn of the input string B is carried out and in that, for each of the items bk, where k ε{0,1, . . . , N−1}, it includes the following steps:
B. arranging in decreasing order the M items ƒi, where i=0, 1, . . . , M−1, of an occurrence vector F of the symbols sm of the alphabet S in at least a portion Wk⊂A of Tk previously calculated items an of the output string A, where Tk≧0, each item ƒi being equal to the number of occurrences in portion Wk of the corresponding symbol shi, in respect of which the following relationship is fulfilled:
7 ∑ i = 0 M - 1 ⁢ f i = T k ,
the items ƒi of the occurrence vector F being arranged in an ordered arrangement vector O comprising M items oj, where j=0, 1, . . . , M−1, whose items oj include the indexes i of items ƒi of vector F arranged in decreasing order, by employing, when two items ƒi are equal, the ordered arrangement of the symbols sm of the alphabet S, as represented by the corresponding ordered arrangement H, such that
ƒox≧ƒoy, ∀y>x
and
for ƒoz=ƒoz+, oz=u<v=oz+1,
where
H={h0, . . . , hu, . . . , hv, . . . , hM−1}
and
C. assigning to item ak of the output string A the symbol
ak=sD(hoj=w)
where w is the w-th index hw of the ordered succession H such as to fulfil the relationship
bk=shw
and the deciphering function D(g) is an invertible function whose dominion and co-dominion are coinciding and are equal to the assembly {0, 1, . . . , M−1}:
8 { m = D ⁢ ⁢ ( g ) ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } g = E ⁡ ( m ) = D - 1 ⁡ ( m ) = ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } [AutoRightMatch] .

15 more elements

A processor comprising processing means for performing the following steps of encoding of input string A into an output string B, both the input string A and the output string B comprising N items, respectively, an and bn, where n=0, 1, . . . , N−1, with items an and bn belonging to an alphabet S of M symbols sm, where m=0, 1, . . . , M−1, the processor performing the steps of:

A. providing an ordered arrangement of the M symbols sm of the alphabet S as represented by a corresponding ordered succession H={hl, where l=1, . . . , M−1} of the indexes m, such that
hlε{0, 1, . . . , M−1}hq≠hr for q≠r,
in that a scanning operation is carried out on items an of the input string A and in that, for each of the items ak, where k ε{0, 1, . . . , N−1}, it includes the following steps:
B. arranging in decreasing order the M items ƒi, where i=0, 1, . . . , M−1, of an occurrence vector F of the symbols sm of the alphabet S in at least a portion Wk⊂A of Tk items an of the input string A, where Tk≧0, each item ƒi being equal to the number of occurrences in portion Wk of the corresponding symbol shi, in respect of which the following relationship is fulfilled:
11 ∑ i = 0 M - 1 ⁢ f i = T k ,
the items ƒi of the occurrence vector F being arranged in an ordered arrangement vector O comprising M items oj, where j=0, 1, . . . , M−1, whose items oj include the indexes i of items ƒi of vector F arranged in decreasing order, by employing, when two items ƒi are equal, the arrangement of the symbols sm of the alphabet S, as represented by the corresponding ordered arrangement H, such that
ƒox≧ƒoy, ∀y>x
and
for ƒoz=ƒoz+1, oz=u<v=oz+1,
where
H={h0, . . . , hu, . . . , hv, . . . , hM−1}
C. establishing a permutation vector P consisting of M items pt, where t=0, 1, . . . , M−1, whose items are such as to fulfil the following relationship
poj=j for j=0, 1, . . . , M−1
and
D. assigning to item bk of the output string B the symbol
bk=sE(hpt=w)
where w is the w-th index hw of the ordered succession H such as to fulfil the relationship
ak=shw
and the enciphering function E(m) is an invertible function whose dominion and co-dominion are coinciding and are equal to the assembly {0, 1, . . . , M−1}:
12 { g = E ⁢ ( m ) ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } m = D ⁢ ( g ) = E - 1 ⁡ ( g ) ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } .

17 more elements

A computer program operating on a computer, the program comprising means for encoding an input string A into an output string B, both the input string A and the output string B comprising N items, respectively, an and bn, where n=0, 1, . . . , N−1, with items an and bn belonging to an alphabet S of M symbols sm, where m=0, 1, . . . , M−1, the means comprising:

means for providing an ordered arrangement of the M symbols sm of the alphabet S as represented by a corresponding ordered succession H={hl, where l=1, . . . , M−1} of the indexes m, such that
hlε{0, 1, . . . , M−1}hq≠hr for q≠r,
in that a scanning operation is carried out on items an of the input string A and in that, for each of the items ak, where k ε{0, 1, . . . , N−1}, it includes the following steps:
arranging in decreasing order the M items ƒi, where i=0, 1, . . . , M−1, of an occurrence vector F of the symbols sm of the alphabet S in at least a portion Wk⊂A of Tk items an of the input string A, where Tk≧0, each item ƒi being equal to the number of occurrences in portion Wk of the corresponding symbol shi, in respect of which the following relationship is fulfilled:
13 ∑ i = 0 M - 1 ⁢ f i = T k ,
the items ƒi of the occurrence vector F being arranged in an ordered arrangement vector O comprising M items oj, where j=0, 1, . . . , M−1, whose items oj include the indexes i of items ƒi of vector F arranged in decreasing order, by employing, when two items ƒi are equal, the arrangement of the symbols sm of the alphabet S, as represented by the corresponding ordered arrangement H, such that
ƒox≧ƒoy, ∀y>x
and
for ƒoz=ƒoz+1, oz=u<v=oz+1, where H={h0, . . . , hu, . . . , hv, . . . , hM−1}
establishing a permutation vector P consisting of M items pt, where t=0, 1, . . . , M−1, whose items are such as to fulfil the following relationship
poj=j for j=0, 1, . . . , M−1
and
assigning to item bk of the output string B the symbol
bk=sE(hpt=w)
where w is the w-th index hw of the ordered succession H such as to fulfil the relationship
ak=shw
and the enciphering function E(m) is an invertible function whose dominion and co-dominion are coinciding and are equal to the assembly {0, 1, . . . , M−1}:
14 { g = E ⁢ ( m ) ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } m = D ⁢ ( g ) = E - 1 ⁡ ( g ) ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } .

15 more elements

A memory medium readable by a computer having a program stored therein, the medium comprising code implementing a method for encoding an input string A into an output string B, both the input string A and the output string B comprising N items, respectively, an and bn, where n=0, 1, . . . , N−1, with items an and bn belonging to an alphabet S of M symbols sm, where m=0, 1, . . . , M−1, the medium comprising:

code for instructing a processor to provide providing an ordered arrangement of the M symbols sm of the alphabet S as represented by a corresponding ordered succession H={hl, where l=1, . . . , M−1} of the indexes m, such that
hlε{0, 1, . . . , M−1}hq≠hr for q≠r,
in that a scanning operation is carried out on items an of the input string A and in that, for each of the items ak, where k ε{0, 1, . . . , N−1}, it includes the following steps:
arranging in decreasing order the M items ƒi, where i=0, 1, . . . , M−1, of an occurrence vector F of the symbols sm of the alphabet S in at least a portion Wk⊂A of Tk items an of the input string A, where Tk≧0, each item ƒi being equal to the number of occurrences in portion Wk of the corresponding symbol shi, in respect of which the following relationship is fulfilled:
15 ∑ i = 0 M - 1 ⁢ f i = T k ,
the items ƒi of the occurrence vector F being arranged in an ordered arrangement vector O comprising M items oj, where j=0, 1, . . . , M−1, whose items oj include the indexes i of items ƒi of vector F arranged in decreasing order, by employing, when two items ƒi are equal, the arrangement of the symbols sm of the alphabet S, as represented by the corresponding ordered arrangement H, such that
ƒox≧ƒoy, ∀y>x
and
for ƒoz=ƒoz+1, oz=u<v=oz+1, where H={h0, . . . , hu, . . . , hv, . . . , hM−1}
establishing a permutation vector P consisting of M items pt, where t=0, 1, . . . , M−1, whose items are such as to fulfil the following relationship
poj=j for j=0, 1, . . . , M−1
and
assigning to item bk of the output string B the symbol
bk=sE(hpt=w)
where w is the w-th index hw of the ordered succession H such as to fulfil the relationship
ak=shw
and the enciphering function E(m) is an invertible function whose dominion and co-dominion are coinciding and are equal to the assembly {0, 1, . . . , M−1}:
16 { g = E ⁢ ( m ) ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } m = D ⁢ ( g ) = E - 1 ⁡ ( g ) ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } .

15 more elements

A processor comprising processing means for performing a method for decoding an input string B into an output string A, both the input string B and the output string A comprising N items, respectively, bn and an, where n=0, 1, . . . , N−1, with items bn and an belonging to an alphabet S of M symbols sm, where m=0, 1, . . . , M−1, the processor comprising means for:

A. providing an ordered arrangement of the M symbols sm of alphabet S represented by a corresponding ordered succession H={hl, where l=0, 1, . . . , M−1} of the indexes m, such that
hlε{0,1, . . . , M−1}hq≠hr, for q≠r,
in that a scanning operation of items bn of the input string B is carried out and in that, for each of the items bk, where k ε{0,1, . . . , N−1}, it includes the following steps:
B. arranging in decreasing order the M items ƒi, where i=0, 1, . . . , M−1, of an occurrence vector F of the symbols sm of the alphabet S in at least a portion Wk⊂A of Tk previously calculated items an of the output string A, where Tk≧0, each item ƒi being equal to the number of occurrences in portion Wk of the corresponding symbol shi, in respect of which the following relationship is fulfilled:
17 ∑ i = 0 M - 1 ⁢ f i = T k ,
the items ƒi of the occurrence vector F being arranged in an ordered arrangement vector O comprising M items oj, where j=0, 1, . . . , M−1, whose items oj include the indexes i of items ƒi of vector F arranged in decreasing order, by employing, when two items ƒi are equal, the ordered arrangement of the symbols sm of the alphabet S, as represented by the corresponding ordered arrangement H, such that
ƒox≧ƒoy, ∀y>x
and
for ƒoz=ƒoz+1, oz=u<v=oz+1, where H={h0, . . . , hu, . . . , hv, . . . , hM−1}
and
C. assigning to item ak of the output string A the symbol
ak=sD(hoj=w)
where w is the w-th index hw of the ordered succession H such as to fulfil the relationship
bk=shw
and the deciphering function D(g) is an invertible function whose dominion and co-dominion are coinciding and are equal to the assembly {0, 1, . . . , M−1}:
18 { m = D ⁡ ( g ) ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } g = E ⁡ ( m ) = D - 1 ⁡ ( m ) ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } .

13 more elements

A computer program operable on a computer that includes code means to perform method for decoding an input string B into an output string A, both the input string B and the output string A comprising N items, respectively, bn and an, where n=0, 1, . . . , N−1, with items bn and an belonging to an alphabet S of M symbols sm, where m=0, 1, . . . , M−1, the computer program comprising code means for:

A. providing an ordered arrangement of the M symbols sm of alphabet S represented by a corresponding ordered succession H={hl, where l=0, 1, . . . , M−1} of the indexes m, such that
hlε{0,1, . . . , M−1}hq≠hr, for q≠r,
in that a scanning operation of items bn of the input string B is carried out and in that, for each of the items bk, where k ε{0,1, . . . , N−1}, it includes the following steps:
B. arranging in decreasing order the M items ƒi, where i=0, 1, . . . , M−1, of an occurrence vector F of the symbols sm of the alphabet S in at least a portion Wk⊂A of Tk previously calculated items an of the output string A, where Tk≧0, each item ƒi being equal to the number of occurrences in portion Wk of the corresponding symbol shi, in respect of which the following relationship is fulfilled:
19 ∑ i = 0 M - 1 ⁢ f i = T k ,
the items ƒi of the occurrence vector F being arranged in an ordered arrangement vector O comprising M items oj, where j=0, 1, . . . , M−1, whose items oj include the indexes i of items ƒi of vector F arranged in decreasing order, by employing, when two items ƒi are equal, the ordered arrangement of the symbols sm of the alphabet S, as represented by the corresponding ordered arrangement H, such that
ƒox≧ƒoy, ∀y>x
and
for ƒoz=ƒoz+1, oz=u<v=oz+1, where H={h0, . . . , hu, . . . , hv, . . . , hM−1}
and
C. assigning to item ak of the output string A the symbol
ak=sD(hoj=w)
where w is the w-th index hw of the ordered succession H such as to fulfil the relationship
bk=shw
and the deciphering function D(g) is an invertible function whose dominion and co-dominion are coinciding and are equal to the assembly {0, 1, . . . , M−1}:
20 { m = D ⁡ ( g ) ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } g = E ⁡ ( m ) = D - 1 ⁡ ( m ) ∈ { 0 , 1 , ⁢ … ⁢ , M - 1 } .

13 more elements

A memory medium readable by a computer having a program stored therein, the memory medium comprising code means for implementing a method for decoding an input string B into an output string A, both the input string B and the output string A comprising N items, respectively, bn and an, where n=0, 1, . . . , N−1, with items bn and an belonging to an alphabet S of M symbols sm, where m=0, 1, . . . , M−1, the memory medium comprising code means for:

A. providing an ordered arrangement of the M symbols sm of alphabet S represented by a corresponding ordered succession H={hl, where l=0, 1, . . . , M−1} of the indexes m, such that
hlε{0,1, . . . , M−1}hq≠hr, for q≠r,
in that a scanning operation of items bn of the input string B is carried out and in that, for each of the items bk, where k ε{0,1, . . . , N−1}, it includes the following steps:
B. arranging in decreasing order the M items ƒi, where i=0, 1, . . . , M−1, of an occurrence vector F of the symbols sm of the alphabet S in at least a portion Wk⊂A of Tk previously calculated items an of the output string A, where Tk≧0, each item ƒi being equal to the number of occurrences in portion Wk of the corresponding symbol shi, in respect of which the following relationship is fulfilled:
21 ∑ i = 0 M - 1 ⁢ ⁢ f i = T k ,
the items ƒi of the occurrence vector F being arranged in an ordered arrangement vector O comprising M items oj, where j=0, 1, . . . , M−1, whose items oj include the indexes i of items ƒi of vector F arranged in decreasing order, by employing, when two items ƒi are equal, the ordered arrangement of the symbols sm of the alphabet S, as represented by the corresponding ordered arrangement H, such that
ƒox≧ƒoy, ∀y>x
and
for ƒoz=ƒoz+1, oz=u<v=oz+1,
where
H={h0, . . . , hu, . . . , hv, . . ., hM−1}
and
C. assigning to item ak of the output string A the symbol
ak=sD(hoj=w)
where w is the w-th index hw of the ordered succession H such as to fulfil the relationship
bk=shw
and the deciphering function D(g) is an invertible function whose dominion and co-dominion are coinciding and are equal to the assembly {0, 1, . . . , M−1}:
22 { m = D ⁡ ( g ) ∈ { 0 , 1 , … ⁢ , M - 1 } g = E ⁡ ( m ) = D - 1 ⁡ ( m ) = ∈ { 0 , 1 , … ⁢ , M - 1 } .

15 more elements

Dependencies are inferred from the claim text.