Method of encoding and transmitting data over a communication medium through division and segmentation

• US 7,304,990 B2
• Filed: 02/02/2001
• Issued: 12/04/2007
• Est. Priority Date: 02/03/2000
• Status: Expired due to Fees

• Current Assignee: Bandwiz, Inc. (Bandwiz, Inc. /Management/)
• Original Assignee: Bandwiz, Inc. (Bandwiz, Inc. /Management/)
• Inventors: Rajwan, Doron
• Primary Examiner(s): Chan; Wing
• Assistant Examiner(s): Cho; Hong Sol
• Application Number:
  US10/049,884
• Publication Number:
  US 20030002533A1
• Time in Patent Office: 2,496 Days
• Field of Search: 370/474, 370/464, 370/389, 370/468, 370/470, 370/32.1, 370/32, 370313-316, 370/221, 370/216, 370/254, 370/225, 370/227, 370/242, 370/244, 370/228, 370/238, 370/289, 375/244, 375/267, 375/347, 375/8, 375/9, 375/27, 375/39, 375/48, 375/51, 375/56, 375/58, 379/410, 379/411, 379/93, 379/97, 379/98, 341/50, 341/51, 341/60, 341/173, 709/231, 709/241, 709/238, 709/239, 709/244, 709/243, 709/204, 714/746, 714/776, 714/22, 714/710, 714/784, 714/781, 714/755, 714/15, 714/756, 714/6, 714/49, 714/7, 714/54, 714/764
• US Class Current: 370/389
• 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.

5. A method according to claim 1, wherein combining comprises adding modulo a field size.

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

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

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

9. A method of preferential encoding of data for transmission over 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.

10. A method according to claim. 9, Wherein said uneven distribution is substantially stepped, having fewer than five different selection probabilities.

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

12. 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.

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

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

15. A method according to claim 12, wherein said selecting comprises randomly selecting.

16. A method according to claim 12, wherein said selecting comprises selecting said subset to include fewer than 50% of said blocks.

17. A method according to claim 12, wherein said transmitted packets define a set of over-constrained equations without a single unique solution.

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

19. 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 below 40% for at least 80% of said blocks;

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.

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

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

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

23. 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.

24. A method according to claim 23, wherein said variation is unknown to said receiver.

25. A method according to claim 23, wherein said variation represents division into buckets.

26. A method according to claim 23, wherein said variation represents preferential encoding.

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

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

29. 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 above 60% for at least 2% of said blocks;

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.

30. 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 below 45% for some packets and above 45% for other packets;

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.