Method and apparatus for decoding non-sequential data packets

• US 5,541,995 A
• Filed: 04/18/1994
• Issued: 07/30/1996
• Est. Priority Date: 04/18/1994
• Status: Expired due to Term

• Current Assignee: Apple Computer Incorporated (Apple Inc.)
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Chu, Ke-Chiang, Normile, James O.
• Primary Examiner(s): Barron, Jr., Gilberto
• Application Number:
  US08/228,725
• Time in Patent Office: 834 Days
• Field of Search: 380/42, 380/43, 380/50, 380/46, 380/48
• US Class Current: 380/42
• 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: H04L 9/40 Network security protocols

Abstract

Data packets which have been sequentially encoded and transmitted, and are received out-of-sequence, are decoded, such that the proper sequence is restored. A receiving decoder is synchronized with a transmitting encoder and generates a sequence of decoding data corresponding to the sequence used to encode the data. The decoding data is combined with the received encoded data to produce the original dam. The decoded data is then stored in message-sequence in a memory. When packet network routing results in the encoded data being received out-of-sequence, a portion of the generated sequence of decoding data corresponding to packets that have not been received is saved in a memory. When the out-of-sequence packet of encoded data is received, the stored portion of the decoding data is retrieved from memory and is combined with the packet data to produce the decoded data, which is then stored in message sequence. In a preferred embodiment, the memories for the decoding data and the stored decoded data are combined and the portion of the decoding data for the packet of unreceived encoded data occupies the memory position reserved for this unreceived data. When this data is received, it is decoded using the stored decoding data and the decoded result replaces the previously unused decoding data in the memory. The invention permits the decoder to be synchronized with the encoder and to generate its sequence of decoding data without regard to the order in which the encoded data packets are received.

Claims

1. An apparatus for decoding sequentially encoded data packets, said packets being received in an unspecified order, the apparatus comprising:

a decoder having a first input for receiving the encoded data packets arriving in an unspecified order, and a second input for receiving sequentially generated decoding data, said decoder defining a correspondence between the sequentially encoded data packets and the sequentially generated decoding data, and combining each received encoded data packet with corresponding decoding data to produce a decoded data packet; and

at least one memory coupled to the decoder, the memory containing the decoded data packets corresponding to encoded data packets which have been received and combined by the decoder, and the memory further containing decoding data received by the decoder and waiting to be combined with corresponding as-yet-unreceived encoded data packets.

2. The apparatus according to claim 1 further including a decoding function generator connected to the decoder that provides and outputs the decoding data to the decoder.

3. The apparatus according to claim 2 wherein the decoding function generator provides a decoding function that is the inverse of an encoding function used to produce the encoded data.

4. The apparatus according to claim 3 wherein the decoder is an exclusive-OR gate.

5. The apparatus according to claim 1 wherein the decoding data is divided into packets.

6. The apparatus according to claim 1 further including a transmitter connected to the decoder that provides and outputs the encoded data packets to the decoder.

7. The apparatus according to claim 1 wherein the memory comprises a first memory section for storing the decoding data and a second memory section for storing the decoded data packets.

9. The apparatus according to claim 1 wherein the decoding of the encoded data comprises decompressing compressed data.

8. The apparatus according to claim I wherein the decoding of the encoded data comprises decrypting encrypted data to produce plaintext data identical to the plaintext data originally encrypted.

10. An apparatus for decoding sequentially encoded data packets, said packets being received in an unspecified order, the apparatus comprising:

means for receiving encoded data packets, arriving in an unspecified order;

a decoding data .generator providing sequentially generated decoding data and defining a correspondence between the sequentially encoded data packets and the sequentially generated decoding data;

means for storing generated decoding data corresponding to as-yet-unreceived encoded data packets for use in decoding encoded data packets received after the .generation of the corresponding decoding data.

11. The apparatus according to claim 10 for decoding encoded data packets further comprising means for storing the decoded data packets received out of the sequential encoding order.

12. The apparatus according to claim 11 for decoding encoded data packets in which the decoded data packets and the generated decoding data are stored in separate means for storing.

13. The apparatus according to claim 10 for decoding encoded data packets, in which the decoding data is generated according to a decoding function.

14. A method for decoding sequentially encoded data packets, said packets being received in an unspecified order, comprising the steps:

receiving encoded data packets, arriving in an unspecified order;

receiving decoding data defining a sequence corresponding to the sequentially encoded data packets;

decoding received encoded data packets for which the corresponding decoding data has been received; and

storing received decoding data corresponding to as-yet-unreceived encoded data packets.

15. The method according to claim 14 for decoding encoded data packets, in which following the step of decoding received encoded data packets, the method further comprises the step of storing the decoded data packets.

16. The method according to claim 15 for decoding encoded data packets, in which the decoded data packets and the generated decoding data are stored in separate memories.

17. The method according to claim 14 for decoding encoded data packets, in which prior to the step of receiving decoding data defining a sequence corresponding to the sequentially encoded data packets, the method further comprises the step of sequentially generating the decoding data according to a decoding function.

18. The method according to claim 17 for decoding encoded data packets, in which the decoding function is the inverse of an encoding function used to produce the encoded data.