Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1999-07-01
2004-07-06
Hua, Ly V. (Department: 2135)
Cryptography
Particular algorithmic function encoding
C713S152000, C370S347000, C370S468000, C370S524000, C455S423000, C380S029000, C380S037000, C380S046000, C380S252000
Reexamination Certificate
active
06760438
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to decoding of digital information sequences and in particular to Viterbi decoding of encrypted digital information sequences.
BACKGROUND OF THE INVENTION
A typical communication scheme includes a transmitter, with a modulator for converting a digital information sequence into a signal, and a receiver, with a demodulator which can recover a digital information sequence from the received signal. A channel, which is between a transmitter and a receiver and may be wireless or wireline, may degrade the signal, through attenuation or the introduction of noise, such that a received sequence differs from the transmitted sequence. The differences between the transmitted and received sequences may be called “errors”. To minimize errors in received sequences, forward error correction coding may be employed through the use of a channel encoder in the transmitter and a channel decoder in the receiver.
Error correction coding is the practice of transmitting additional redundant bits besides the digital information sequence such that a receiver may determine if the received sequence is the same as the sent sequence and, if not, correct the received sequence. The coding may be applied intermittently to “blocks” of bits, continuously to bits in a bit stream or employ a combination of the two methods. One form of continuous coding is “convolutional coding” in which a series of bits at the output of a channel encoder represent a result of operations performed on a set number of input bits. In a rate ½ convolutional encoder, a series of two new output bits are generated for each input bit. Along with the rate of a convolutional encoder, another characteristic is a constraint length. The constraint length indicates the number of inputs that are operated upon to generate each output. A rate ½ convolutional encoder which outputs two bits v
1
and v
2
for each input u
t
has a “constraint length” of 3 if bits v
1
and v
2
are based on operations performed on u
t
and the two bits previous to u
t
, u
t-1
and u
t-2
. For example, we could have v
1
=u
t
+u
t-1
+u
t-2
and v
2
=u
t
+u
t-2
, where “+” represents modulo-2 addition.
A digital information sequence which has been subject to error correction coding must be decoded at the receiver. An optimum maximum likelihood decoder, for this type of coding, determines a sequence of bits which has a maximum likelihood of being the sequence that was sent. The Viterbi algorithm is a maximum likelihood decoding scheme for use at a receiver where an information sequence has employed an encoder using convolutional codes and the channel is an additive white Gaussian noise channel.
In general, channel decoding can be performed in two ways, namely, hard-decision decoding in a hard bit domain and soft-decision decoding in a soft bit (symbol) domain. Usually, samples of the demodulated signal are quantized resulting in bits so that, at the output of a demodulator, decoding can be performed in a bit-wise manner. In the hard bit domain, the demodulator quantizes each sample to one of two levels, i.e. 0 or 1, and is said to have made a hard-decision. The decoder that works with this kind of input is said to perform hard-decision decoding. On the other hand, if quantization is performed using more than two levels per bit, the resulting quantized samples are called soft symbols, or simply, symbols. The decoder making use of the information in soft-symbols is performing soft-decision decoding.
Hard-decision decoding has the advantage of less computational complexity than soft-decision decoding due to binary bit-wise operation. However, some useful information is lost during quantization. Therefore, hard-decision decoding does not perform very well under certain circumstances including, for example, a distorted channel, which is the case for real wireless communication systems.
A soft-decision decoder receives soft-decision inputs, which makes it more complex to implement. However, soft-decision decoding offers significantly better performance than hard-decision decoding. It has been reported that, to achieve the same error probability, at least 2 dB more signal power must be generated at the transmitter when the demodulator provides a hard-decision output, assuming an Additive White Gaussian Noise (AWGN) channel (see, for example, S. Lin and D. J. Costello Jr., “Error Control Coding: Fundamentals and Applications”, Prentice-Hall, 1983, which is incorporated herein by reference). In other words, there is a 2 dB or more improvement for soft-decision decoding in an AWGN channel. In addition, this improvement implies an increment of the capacity in a cellular system, an important issue in the wireless industry.
U.S. Pat. No. 5,802,116 issued Sep. 1, 1998 to Baker et al. presents a method and apparatus for obtaining a soft symbol decoded output of a received signal by a two pass Viterbi operation. In a first pass the received signal is hard decision decoded. In a second pass the received signal is soft decision decoded with previously decoded hard bit information used as a most likely next state at a given time instant. This method sacrifices time in order to conserve memory required to store all possible next states at a given time instant.
A soft decision decoding receiver is disclosed in U.S. Pat. No. 5,844,946 issued Dec. 1, 1998 to Nagayasu. Used to reduce errors in channels which causes intersymbol interference (ISI), the receiver uses a training sequence to estimate the ISI present and uses the estimation to derive a replica of a received signal. The actual received signal and the replica are compared to generate a local metric for a particular path from a state at one time instant to a next state. The local metric is then used in a maximum likelihood decoding algorithm such as the Viterbi algorithm to obtain a decoded bit sequence.
The above patents are but two of a large volume of patents related to channel decoding. It should be noted that neither contemplate using soft decision decoding in conjunction with encryption.
In cellular telephony, the channel is a wireless connection from a mobile telephone to a relatively nearby base station. Despite channel coding, a properly equipped individual may “listen in” to conversations taking place over the channel. For this reason, a digital representation of a voice message may be encrypted.
Encryption in cellular telephony has drawn attention recently due to an increased requirement for personal privacy, electronic commerce and prevention of cellular phone fraud. Standards for digital mobile telephony were developed to include voice ciphering and signalling message and data encryption (see, for example, Electronics Industries Association/Telecommunication Industries Association (EIA/TIA) Interim Standard 95 (IS-95) for Code Division Multiple Access (CDMA) and Interim Standard (IS-136) for Time Division Multiple Access (TDMA)). In IS-136, encryption is applied after error correction coding of the speech signal and before modulation.
In a typical communication scheme, an encryption operation is performed before modulation in the transmitter and a decryption operation is performed after demodulation in the receiver. Current encryption schemes depend on this placement as encryption and decryption are performed in a binary bit-wise manner. For example, an encryption operation could comprise performing an exclusive-OR (XOR) operation with an encryption mask and the encoded information sequence as operands. The following is a truth table for the XOR (⊕) operation.
A
B
A ⊕ B
0
0
0
0
1
1
1
0
1
1
1
0
If soft-decision decoding is used in the receiver, the input to the soft-decision decoder must be soft-decision samples instead of binary bits. This requires the demodulator make a soft-decision to obtain output symbols, for example, a multi-level quantized real number, 0.75, or a complex number, exp(j3&pgr;/8). As a result, the input and output of the decryption process may be in soft symbol format. As discussed, current enc
Hui Yan
Mann Karl D.
Hua Ly V.
Nortel Networks Limited
LandOfFree
System and method for Viterbi decoding on encrypted data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for Viterbi decoding on encrypted data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for Viterbi decoding on encrypted data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3192589