Coding method

• US 20030002533A1
• Filed: 02/12/2002
• Published: 01/02/2003
• Est. Priority Date: 02/03/2000
• Status: Active Grant

• Current Assignee: Bandwiz, Inc. (Bandwiz, Inc. /Management/)
• Original Assignee: Bandwiz, Inc. (Bandwiz, Inc. /Management/)
• Inventors: Rajwan, Doron
• Granted Patent: US 7,304,990 B2
• Time in Patent Office: Days
• US Class Current: 370/474
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/007 Unequal error protection for format H04L1/0078; for codes per se H03M13/35

Abstract

A method of encoding and transmitting data over a communication medium, comprising, providing a file; dividing said file into a plurality of buckets; segmenting each bucket into a et of blocks; selecting a subset of blocks from a bucket; generating a packet by combining said selected blocks, such that an individual block cannot be reconstructed from a single packet; repeating said selecting and said generating for a plurality of buckets and a plurality of packets; generating at last one cross-bucket packet by combining blocks from different buckets and transmitting said generated packets and said generated cross-packets, said packets and said cross-packets being marked as such

Claims

1. A method of encoding and transmitting data over a communication medium, comprising:

providing a file;

dividing said file into a plurality of buckets;

segmenting each bucket into a set of blocks;

selecting a subset of blocks from a bucket;

generating a packet by combining said selected blocks, such that an individual block cannot be reconstructed from a single packet;

repeating said selecting and said generating for a plurality of buckets and a plurality of packets;

generating at least one cross-bucket packet by combining blocks from different buckets; and

transmitting said generated packets and said generated cross-packets, said packets and said cross-packets being marked as such.

2. A method according to claim 1, wherein selecting said blocks comprises selecting fewer than 50% of the blocks in the bucket for said packet.

3. A method according to claim 1, wherein transmitting comprises transmitting for each packet an indication of the blocks participating in said packet.

4. A method according to claim 1, comprising generating cross-cross-packets, which include contributions from multiple cross-bucket packets.

41. A method according to any of claims 1-36, wherein combining comprises adding modulo a field size.

42. A method according to claim 41, wherein said field size is 2 for at least some of the packets.

43. A method according to claim 41, wherein said field size is greater than 2 for at least some of the packets.

44. A method according to claim 41, wherein said field size is greater than 2 only for some of the packets.

46. A method according to claim 45, wherein said generating comprises generating by randomly selecting blocks of said data file to be included in packets.

5. A method of differential-decoding, comprising:

receiving and reconstructing at least a first part of a data file from a transmitter; and

determining data missing relative to said file;

receiving from a data stream transmitted independently of said missing data, substantially only enough data packets required to decode said missing data; and

reconstructing said missing data from said data packets, using said previously received first part of the file, wherein an identification of at least one of said received at least part of a file and said missing data is not known to said transmitter.

6. A method according to claim 5, wherein said data stream is transmitted to a plurality of receivers have different missing data.

7. A method according to claim 5, wherein said data is encoded using a FEC (forward error correction) code.

8. A method according to claim 5, wherein said reconstructing comprises reconstructing using data reconstructed from said part of a file.

9. A method according to claim 5, wherein said reconstructing comprises reconstructing using data packets previously received for said part of a file.

10. A method according to claim 5, comprising, generating said data stream for a plurality of different receivers with different missing data.

11. A method of preferential encoding of data for transmission over a communication medium, comprising:

providing at least a portion of a file as a plurality of blocks;

selecting a subset of blocks from said file;

generating a packet by combining said blocks, such that an individual block cannot be reconstructed from a single packet; and

repeating said selecting and said generating for a plurality of packets,

wherein said blocks are selected in an uneven selection distribution, such that blocks with a higher priority are selected more often to take part in a packet.

12. A method according to claim 11, wherein said uneven distribution is substantially stepped, having fewer than five different selection probabilities.

13. A method according to claim 11, wherein said uneven distribution is substantially continuous, having more than 5 different selection probabilities.

15. A method according to claim 14, wherein said repetition continues for after at least 10 times the required number of packets are transmitted.

16. A method according to claim 14, wherein said repetition continues for after at least 50 times the required number of packets are transmitted.

17. A method according to claim 14 or claim 15, wherein said selecting comprises randomly selecting.

18. A method according to claim 14 or claim 15, wherein said selecting comprises selecting said subset to include fewer than 50% of said blocks.

19. A method according to claim 14 or claim 15, wherein said transmitted packets define a set of over-constrained equations without a single unique solution.

20. A method according to claim 14 comprising maintaining said channel as open as long as there exists a requester for said file.

14. A method of encoding data for transmission over a communication medium, comprising:

providing at least a portion of a file as a plurality of blocks;

selecting a subset of said blocks;

generating a packet by combining said blocks, such that an individual block cannot be reconstructed from a single packet;

transmitting said packet over an open channel;

repeating said selecting, said generating and said transmitting as long as said channel is open and after at least twice as many packets as required for reconstructing the file are transmitted.

21. A method of encoding data for transmission over a communication medium, comprising:

providing at least a portion of a file as a plurality of blocks;

randomly selecting a subset of said blocks, said selecting comprising selecting a block at a probability of other than 50%;

generating a packet by combining said blocks, such that an individual block cannot be reconstructed from a single packet; and

repeating said selecting and said generating for a plurality of packets.

22. A method according to claim 21, wherein said probability is above 60% for at least 2% of said blocks.

23. A method according to claim 21, wherein said probability is below 40% for at least 80% of said blocks.

24. A method according to claim 21, wherein said probability is below 20% for at least 80% of said blocks.

25. A method according to claim 21, wherein said probability is below 10% for at least 80% of said blocks.

26. A method according to claim 21, wherein said probability is below 5% for at least 80% of said blocks.

27. A method according to claim 21, wherein said probability is below 45% for some packets and above 45% for other packets.

29. A method according to claim 28, comprising displaying at least part of said reconstructed portion, prior to receiving said sufficient packets.

30. A method according to claim 28, comprising storing at least part of said reconstructed portions in the place of said solved equations.

31. A method according to claim 28, wherein each of said packets is not limited to include contributions from only part of said data file.

32. A method according to claim 28, comprising attempting to solve said equations to determine if at least some of said equations can be solved.

33. A method according to claim 28, comprising attempting to solve said equations only after a certain percentage of said sufficient packets are received.

34. A method according to claim 28, comprising utilizing equations defined between groups of packets for said solving.

36. A method according to claim 35, wherein said variation is unknown to said receiver.

37. A method according to claim 35, wherein said variation represents division into buckets.

38. A method according to claim 35, wherein said variation represents preferential encoding.

39. A method according to claim 35, wherein said variation represents changes in block selection probability per packet.

40. A method according to claim 35, wherein said variation represents providing a cross-bucket packet rather than a regular packet.

28. A method of decoding, comprising:

receiving a plurality of packets encoding a data file;

setting up, in a memory, a set of equations whose solution represents the data file, based on a content of said packets; and

solving only some of said equations before receiving sufficient packets for setting up all the equations required to determine said data file, to reconstruct a portion of said data file.

35. A method of transmitting information, comprising:

providing at least a portion of a file as a plurality of blocks;

selecting a subset of said blocks;

generating a packet by combining said blocks, such that an individual block cannot be reconstructed from a single packet, said packets varying in an a-priori probability of a block being selected for inclusion in a packet.

transmitting said packet;

repeating said selecting, said generating and said transmitting for a plurality of packets;

receiving at least some of said packets; and

reconstructing said at least a portion of the file from said received packets.

45. A method of storing information on a storage media, comprising:

determining an expected error rate on said storage media;

encoding a data file to be stored as a plurality of FEC (forward error correction) coded packets, including;

selecting a number of packets required to overcome said error rate; and

generating said number of packets;

writing said packets to said storage media.