System and method for Viterbi decoding on encrypted data

• US 6,760,438 B1
• Filed: 07/01/1999
• Issued: 07/06/2004
• Est. Priority Date: 07/01/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Hui, Yan, Mann, Karl D.
• Primary Examiner(s): HUA, LY
• Application Number:
  US09/345,419
• Time in Patent Office: 1,832 Days
• Field of Search: 380/28, 380/29, 380/37, 380/45, 380/46, 380/252, 380/262, 380/266, 380/269, 380/270, 713/200, 713/159, 375/133, 375/148, 375/152, 375/366, 370/347, 370/468, 370/524, 455/423, 455/425
• US Class Current: 380/28
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0054 Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms
• CPC Class Codes: H04L 1/006 Trellis-coded modulation
• CPC Class Codes: H04L 1/0065 Serial concatenated codes
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27
• CPC Class Codes: H04L 2001/0098 Unequal error protection
• CPC Class Codes: H04L 2209/046 of operations, operands or results of the operations
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/065 Encryption by serially and continuously modifying data stream elements, e.g. stream cipher systems, RC4, SEAL or A5/3
• CPC Class Codes: Y04S 40/20 Information technology specific aspects, e.g. CAD, simulation, modelling, system security

Abstract

A system and method for Viterbi decoding on encrypted data is disclosed. At the receiver, maximum likelihood decoding is performed based on received input in the encryption domain. When selecting a path from one stage of a Viterbi decoding trellis to the next, a local metric may be associated with each of the possible paths based on Euclidean distance between a received symbol and a path state. The path state is determined by encrypting the binary path state. An overall metric is associated with each state equivalent to a sum of local path metrics along a survivor path of selected paths. At the end of the Viterbi decoding trellis, a decoded and decrypted bit sequence is obtained by tracing back in a conventional manner.

Claims

1. A method to be employed during channel decoding, said method comprising:

obtaining a channel decoding trellis having states, stages, and paths between states of adjacent stages, each of said paths having an associated path state;

encrypting each said path state with an encryption mask to result in an encrypted path state.

2. In a channel decoding trellis comprising states and paths between said states, a method for selecting one path from a plurality of paths leading to a destination state comprising:

for each path of said plurality of paths leading to said destination state,

encrypting a path state, associated with said each path, with an encryption mask to result in an encrypted path state;

determining a local metric from an input and said encrypted path state;

associating said local metric with said each path;

associating an overall path metric with said each path, where said overall pat metric is equivalent to a sum of said local metric associated with said each path and an overall state metric associated with a state at the origin of said path; and

selecting one path of said plurality of paths leading to said destination state based, at least in part, on each said overall path metric associated with said each path.

3. The method of claim 2 wherein said input is in a symbol domain and said local metric determining further comprises mapping said encrypted path state to said symbol domain to result in a encrypted soft path state.

4. The method of claim 3 wherein said local metric determining comprises determining a Euclidean distance between said input and said encrypted soft path state and basing said local metric, at least in part, on said Euclidean distance.

5. The method of claim 4 wherein said local metric determining further comprises squaring said Euclidean distance between said input and said encrypted soft path state to obtain a square of said Euclidean distance and basing said local metric, at least in part, on said square of said Euclidean distance.

6. The method of claim 2 wherein said encryption mask corresponds to a current time.

7. The method of claim 2 wherein said path state consists of a bit sequence and said encryption mask is a bit sequence with the same number of bits as said path state.

8. The method of claim 7 wherein said encrypting comprises performing an exclusive or operation with said encryption mask and said path state as operands.

9. A decoder including a processor for selecting one path from a plurality of paths leading to a destination state, said plurality of paths in a channel decoding trellis comprising states and paths between said states, said processor comprising:

means for encrypting a path state, associated with said each path, with an encryption mask to result in an encrypted path state;

means for determining a local metric from an input and said encrypted path state;

means for associating said local metric with said each path; and

means for associating an overall path metric with said each path, where said overall path metric is equivalent to a sum of said local metric and an overall state metric associated with a state at the origin of said path; and

means for selecting one path of said plurality of paths leading to said destination state based at least in part on each said overall path metric.

10. A communication system comprising

an encoder;

an encryption unit receiving input from said encoder;

a modulator receiving input from said encryption unit;

a channel receiving input from said modulator;

a demodulator receiving input from said channel;

a signal processor, receiving input from said demodulator, comprising;

means for encrypting a path state, associated with said each path, with an encryption mask to result in an encrypted path state;

means for determining a local metric from an input and said encrypted path state;

means for associating said local metric with said each path;

means for associating an overall path metric with said each path, where said overall path metric is equivalent to a sum of said local metric and an overall state metric associated with a state at the origin of said path; and

means for selecting one path of said plurality of paths leading to said destination state based at least in part on each said overall path metric.

11. A communication system comprising

an encoder;

an encryption unit receiving input from said encoder;

an interleaver receiving input from said encryption unit;

a modulator receiving input from said interleaver;

a channel receiving input from said modulator;

a demodulator receiving input from said channel;

a deinterleaver receiving input from said demodulator;

a signal processor, receiving soft decision input from said deinterleaver, comprising;

means for encrypting a path state, associated with said each path, with an encryption mask to result in an encrypted path state;

means for determining a local metric from an input and said encrypted path state;

means for associating said local metric with said each path;

means for associating an overall path metric with said each path, where said overall path metric is equivalent to a sum of said local metric and an overall state metric associated with a state at the origin of said path; and

means for selecting one path of said plurality of paths leading to said destination state based at least in part on each said overall path metric.

12. A computer readable medium for providing program control for a processor in a communications system, said processor for selecting one path from a plurality of paths leading to a destination state, said plurality of paths in a channel decoding trellis comprising states and paths between said states, said processor operable to:

for each path of said plurality of paths leading to said destination state,

encrypt a path state, associated with said each path, with an encryption mask to result in an encrypted path state;

determine a local metric from an input and said encrypted path state;

associate said local metric with said each path; and

associate an overall path metric with said each path, where said overall path metric is equivalent to a sum of said local metric and an overall state metric associated with a state at the origin of said path; and

select one path of said plurality of paths leading to said destination state based at least in part on each said overall path metric.

13. A method to be employed during decrypting and decoding encrypted coded soft symbols, said method comprising:

associating a given encrypted encoded soft symbol with at least one stage and state of a decoding trellis, each path of said decoding trellis having an associated soft symbol path state and an equivalent hard symbol path state;

obtaining an encryption mask for use in decrypting said given encrypted encoded soft symbol;

encrypting said equivalent bard symbol path state in said decoding trellis associated with each path leading to said at least one stage and state, utilising said encryption mask;

determining an encrypted soft symbol path state corresponding to each encrypted equivalent hard symbol path state; and

determining metrics, each based on said given encrypted encoded soft symbol and one said encrypted soft symbol path state.

14. A decoder for use in decrypting and decoding encrypted coded soft symbols, comprising:

means for associating a given encrypted encoded soft symbol with at least one stage and state of a decoding trellis, each path of said decoding trellis having an associated soft symbol path state and an equivalent hard symbol path state;

means for obtaining an encryption mask for use in decrypting said given encrypted encoded soft symbol;

means for encrypting said equivalent hard symbol path state in said decoding trellis associated with each path leading to said at least one stage and state, utilising said encryption mask;

means for determining an encrypted soft symbol path state corresponding to each encrypted equivalent hard symbol path state; and

means for determining metrics, each based on said given encrypted encoded soft symbol and one said encrypted soft symbol path state.

15. A method to be employed during decrypting and decoding encrypted coded symbols, said method comprising:

associating a given encrypted encoded symbol with at least one stage and state of a decoding trellis, each path of said decoding trellis having an associated symbol path state which, where said trellis is in a hard symbol domain, is a hard symbol path state and which, where said trellis is in a soft symbol domain, is a soft symbol path state with an equivalent hard symbol path state;

obtaining an encryption mask for use in decrypting said given encrypted encoded symbol;

encrypting said hard symbol path state in said decoding trellis associated with each path leading to said at least one stage and state, utilising said encryption mask; and

determining metrics utilising said given encrypted encoded symbol and each said encrypted hard symbol path state.

16. A decoder for use in decrypting and decoding encrypted coded symbols, comprising:

means for associating a given encrypted encoded symbol with at least one stage and state of a decoding trellis, each path of said decoding trellis having an associated symbol path state which, where said trellis is in a hard symbol domain, is a hard symbol path state and which, where said trellis is in a soft symbol domain, is a soft symbol path state with an equivalent bard symbol path state;

means for obtaining an encryption mask for use in decrypting said given encrypted encoded symbol;

means for encrypting said hard symbol path state in said decoding trellis associated with each path leading to said at least one stage and state, utilising said encryption mask; and

means for determining metrics utilising said given encrypted encoded symbol and each said encrypted hard symbol path state.

17. A method to be employed by a decoder, said method comprising:

obtaining an encryption mask;

in a decoding trellis having an associated soft symbol path state and an equivalent hard symbol path state,

determining a destination state corresponding with said encryption mask; and

encrypting said equivalent hard symbol path state associated with each path leading to said destination state utilising said encryption mask; and

determining an encrypted soft symbol path state corresponding to each encrypted equivalent hard symbol path state.

18. A decoder comprising:

means for obtaining an encryption mask;

in a decoding trellis having an associated soft symbol path state and an equivalent hard symbol path state,

means for determining a destination state corresponding with said encryption mask and

means for encrypting said equivalent hard symbol path state associated with each path leading to said destination state utilising said encryption mask; and

means for determining an encrypted soft symbol path state corresponding to each encrypted equivalent hard symbol path state.

19. A decoder including a processor for selecting one path from a plurality of paths leading to a destination state, said plurality of paths in a channel decoding trellis comprising states and paths between said states, said processor operable to:

encrypt a path state, associated with each path of said plurality of paths, with an encryption mask lo result in an encrypted path state;

determine a local metric from an input and said encrypted path state;

associate said local metric with said each path; and

associate an overall path metric with said each path, where said overall path metric is equivalent to a sun of said local metric and an overall state metric associated with a state at the origin of said path; and

select one path of said plurality of paths leading to said destination state based at least in part on each said overall path metric.

20. A communication system comprising

an encoder;

an encryption unit receiving input from said encoder;

a modulator receiving input from said encryption unit;

a channel receiving input from said modulator;

a demodulator receiving input from said channel;

a signal processor, receiving input from said demodulator, operable to;

encrypt a path state, associated with each path of a plurality of paths in a channel decoding trellis leading to a destination state, with an encryption mask to result in an encrypted path state;

determine a local metric from an input and said encrypted path state;

associate said local metric with said each path;

associate an overall path metric with said each path, where said overall path metric is equivalent to a sum of said local metric and an overall state metric associated with a state at the origin of said path; and

select one path of said plurality of paths leading to said destination state based at least in part on each said overall path metric.

21. A communication system comprising

an encoder;

an encryption unit receiving input from said encoder;

an interleaver receiving input from said encryption unit;

a modulator receiving input from said interleaver;

a channel receiving input from said modulator;

a demodulator receiving input from said channel;

a deinterleaver receiving input from said demodulator;

a signal processor receiving soft decision input from said deinterleaver, operable to;

encrypt a path state, associated with each path of a plurality of paths in a channel decoding trellis leading to a destination state, with an encryption mask to result in an encrypted path state;

determine a local metric from an input and said encrypted path state;

associate said local metric with said each path;

associate an overall path metric with said each path, where said overall path metric is equivalent to a sum of said local metric and an overall state metric associated with a state at the origin of said path; and

select one path of said plurality of paths leading to said destination state based at least in part on each said overall path metric.

22. A decoder for use in decrypting and decoding encrypted coded soft symbols, said decoder operable to:

associate a given encrypted encoded soft symbol with at least one stage and state of a decoding trellis, each path of said decoding trellis having an associated soft symbol path state and an equivalent hard symbol path state;

obtain an encryption mask for use in decrypting said given encrypted encoded soft symbol;

encrypt said equivalent hard symbol path state in said decoding trellis associated with each path leading to said at least one stage and state, utilising said encryption mask;

determine an encrypted soft symbol path state corresponding to each encrypted equivalent hard symbol path state; and

determine metrics, each based on said given encrypted encoded soft symbol and one said encrypted soft symbol path state.

23. A decoder for use in decrypting and decoding encrypted coded symbols, said decoder operable to:

associate a given encrypted encoded symbol with at least one stage and state of a decoding trellis, each path of said decoding trellis having an associated symbol path state which, where said trellis is in a hard symbol domain, is a hard symbol path state and which, where said trellis is in a soft symbol domain, is a soft symbol path state with an equivalent hard symbol path state;

obtain an encryption mask for use in decrypting said given encrypted encoded symbol;

encrypt said hard symbol path state in said decoding trellis associated with each path leading to said at least one stage and state, utilising said encryption mask; and

determine metrics utilising said given encrypted encoded symbol and each said encrypted hard symbol path state.

24. A decoder operable to:

obtain an encryption mask;

in a decoding trellis having an associated soft symbol path state and an equivalent hard symbol path state,

determine a destination state corresponding with said encryption mask and

encrypt said equivalent hard symbol path state associated with each path leading to said destination state utilising said encryption mask; and

determine an encrypted soft symbol path state corresponding to each encrypted equivalent hard symbol path state.

25. A computer readable medium containing computer-executable instructions that, when performed by a processor in a communications system, said processor for selecting one path from a plurality of paths leading to a destination state, said plurality of paths in a channel decoding trellis comprising states and paths between said states, cause said processor:

for each path of said plurality of paths leading to said destination state,

encrypt a path state, associated with said each path, with an encryption mask to result in an encrypted path state;

determine a local metric from an input and said encrypted path state;

associate said local metric with said each path; and

associate an overall path metric with said each path, where said overall path metric is equivalent to a sun of said local metric and an overall state metric associated with a state at the origin of said path; and

select one path of said plurality of paths leading to said destination state based at least in part on each said overall path metric.