최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
DataON 바로가기다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
Edison 바로가기다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
Kafe 바로가기국가/구분 | United States(US) Patent 등록 |
---|---|
국제특허분류(IPC7판) |
|
출원번호 | US-0197993 (2008-08-25) |
등록번호 | US-9136878 (2015-09-15) |
발명자 / 주소 |
|
출원인 / 주소 |
|
대리인 / 주소 |
|
인용정보 | 피인용 횟수 : 0 인용 특허 : 222 |
A method of encoding data operates on an ordered set of input symbols and includes generating redundant symbols from the input symbols, and includes generating output symbols from a combined set of symbols including the input symbols and the redundant symbols, wherein the number of possible output s
A method of encoding data operates on an ordered set of input symbols and includes generating redundant symbols from the input symbols, and includes generating output symbols from a combined set of symbols including the input symbols and the redundant symbols, wherein the number of possible output symbols is much larger than the number of the combined set of symbols, wherein at least one output symbol is generated from more than one symbol in the combined set of symbols and from less than all of the symbols in the combined set of symbols. The redundant symbols are generated from an ordered set of input symbols in a deterministic process such that a first set of static symbols calculated using a first input symbol has a low common membership with a second set of static symbols calculated using a second input symbol distinct from the first input symbol.
1. A method of encoding data for transmission from a source to a destination over a communications channel, wherein the data is represented at least by a plurality, K, of source symbols, K being the number of source symbols and the source symbols being in an ordered set, the method comprising: gener
1. A method of encoding data for transmission from a source to a destination over a communications channel, wherein the data is represented at least by a plurality, K, of source symbols, K being the number of source symbols and the source symbols being in an ordered set, the method comprising: generating one or more repair symbols from the plurality of source symbols;transmitting one or more output symbols over the communications channel, wherein the communication channel is a channel that can introduce errors in transmissions, wherein an output symbol corresponds to either a source symbol or a repair symbol;determining a desired degree of accuracy for a regeneration of source symbols;determining, for each of a plurality of source symbols, an associated symbol relation that is a function of a systematic index, J(K), where J(K) is a function of K;determining L intermediate symbol values using a function that takes as its input, at least in part, (1) values of at least some of the K source symbols and (2) the associated symbol relations of those at least some of the K source symbols, and (3) a set of L-K pre-coding relations, wherein L is at least K; anddetermining a value for each repair symbol using the associated symbol relation for that repair symbol and the plurality of L intermediate symbol values;wherein the encoding is such that the plurality of source symbols can be regenerated to the desired degree of accuracy from a predetermined number, N, of the transmitted output symbols. 2. The method of claim 1, further comprising precalculating and storing the systematic index J(K) in a table for each value of K. 3. The method of claim 1, wherein the systematic index J(K) is equal to 18, 14, 43, 55, 41, 88, 213, 415, and 2665 for values of K equal to 4, 8, 16, 64, 128, 512, 1024, 4096, and 8192, respectively. 4. The method of claim 1, wherein the symbol relations impose linear constraints on sets of source symbols. 5. The method of claim 4, wherein the linear constraints are exclusive-or constraints. 6. The method of claim 1, wherein each source symbol has an associated encoding symbol identifier (“ESI”) that identifies the symbol, wherein the systematic index J(K) and a value X, wherein X is a valid ESI, determines the symbol relation for the source symbol identified by ESI X. 7. The method of claim 6, wherein the systematic index J(K) and the ESI X can be used to generate a triple (a[X],b[X],d[X]) that defines the source symbol relation for the symbol identified by ESI X. 8. The method of claim 6, wherein each source symbol can be identified by an integer ESI in the range 0 to K−1, inclusive. 9. The method of claim 6, wherein each repair symbol can be identified by an integer ESI that is at least K. 10. The method of claim 7, wherein the triple (a[X],b[X],d[X]) that defines the source symbol relation associated with the source symbol with ESI X places a linear constraint on the value C′[X] for source symbol with ESI X and the values C[0], C[1], . . . , C[L−1] of the L intermediate symbols, the linear constraint defined by the method comprising: defining an array of positive integer values B[0], . . . , B[J−1], wherein J is the minimum of d[X] and L, wherein L′ is the smallest integer that is prime that is at least the value of L, and wherein the values of the array of positive integer values B[0], . . . , B[J−1] are set using the method comprising: (a) setting the initial value of B[0] to b[X];(b) while B[0] is at least L, recalculating B[0] as the previous value of B[0] plus a[X] modulo L′;(c) for values of j starting at 1 and going up to J−1 in increments of one,(d) initializing the value of B[j] to B[j−1] plus a[X]; and(e) while B[j] is at least L, recalculating B[j] as the previous value of B[j] plus a[X] modulo L′. 11. The method of claim 7, further comprising: calculating a value A as (53591+J(K)*997) % 65521, wherein * is the multiplication operator and % is the modulo operator;calculating a value B as 10267*(J(K)+1) % 65521;calculating a value Y as (B+X*A) % 65521; anddetermining a value v, wherein v is in the range from 0 and 1048575, inclusive, where v is calculated as the output of a random generator applied to the inputs Y, 0, and 1048575. 12. The method of claim 11 further comprising: determining d[X] based on a degree function applied to the input v. 13. The method of claim 11 further comprising: determining a[X], wherein a[X] is in the range between 0 and L′−1, inclusive, wherein L′ is the smallest prime number greater than or equal to L, wherein L′ is calculated as one plus the output of the random generator applied to the inputs Y, 1 and L′−1. 14. The method of claim 11 further comprising: determining b[X], wherein b[X] is in the range between 0 and L′, inclusive, wherein b[X] is calculated as the output of the random generator applied to the input Y, 2 and L′. 15. The method of claim 11, wherein the value of d[X] is determined based on v as follows: if the value of v is between 0 and 10240, inclusive, then the value of d[X] is 1,if the value of v is between 10241 and 4911581, inclusive, then the value of d[X] is 2,if the value of v is between 4911582 and 712793, inclusive, then the value of d[X] is 3,if the value of v is between 712794 and 831694, inclusive, then the value of d[X] is 4,if the value of v is between 831695 and 948445, inclusive, then the value of d[X] is 10,if the value of v is between 948446 and 1032188, inclusive, then the value of d[X] is 11,if the value of v is between 1032189 and 1048575, inclusive, then the value of d[X] is 40. 16. The method of claim 11, wherein the random generator on inputs Y, i, and m is calculated as (V0[(Y+i) % 256]^(V1[(floor(Y/256)+i) % 256]) % m, where % is the modulo operator, ^ is the exclusive-or operator, / is the division operator, floor calculates the largest integer that is at most the input value, and V0 and V1 are each tables of 256 integers chosen randomly or pseudo-randomly. 17. The method of claim 16, wherein table V0 has values, in decimal representation, of 3067016507, 689605112, 4005368743, 4048876515, 778296777, 2669179716, 3457502702, 4291353919, 2687243553, 2068983570, 616452097, 3272161958, 234652930, 179350258, 2054995199, and 1358307511 for table indices of 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, and 256, respectively, when a first entry of table V0 has a table index of 1. 18. The method of claim 16, wherein table V1 has values, in decimal representation, of 4114760273, 3302235057, 640417429, 852173610, 4071072948, 3904109414, 3123492423, 3870972145, 2712821515, 4267074718, 4259411376, 1351086955, 4187322100, 2822905141, 3762994475, and 4135048896 for table indices of 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, and 256, respectively, when a first entry of table V1 has a table index of 1. 19. The method of claim 1, wherein the number L-K of pre-coding relations comprises a first set of S pre-coding relations and a second set of H pre-coding relations, and wherein the L intermediate symbols comprises a first set of K intermediate symbols, a second set of S intermediate symbols, and a third set of H intermediate symbols. 20. The method of claim 19, wherein each pre-coding relation in the first set of pre-coding relations is uniquely associated with an intermediate symbol in the second set of intermediate symbols and is associated with a specified set of intermediate symbols among the first set of intermediate symbols, wherein each pre-coding relation is a linear constraint on the value of the associated intermediate symbol and the values of the intermediate symbols in the specified set. 21. The method of claim 20, wherein the linear constraint is an exclusive-or constraint. 22. The method of claim 20, wherein for each first pre-coding relation among the first set of pre-coding relations and for each second pre-coding relation among the first set of pre-coding relations, the number of intermediate symbols that are both in the specified set associated with the first pre-coding relation and in the specified set associated with the second pre-coding relation is at most 3. 23. The method of claim 20, wherein each of the intermediate symbols in the first set of intermediate symbols is in the specified set of exactly three of the pre-coding relations in the first set of pre-coding relations. 24. The method of claim 19, wherein S is the smallest prime integer that is at least as large as 0.01*K+X, wherein X is the smallest positive integer such that X*(X−1) is at least 2*K,wherein H is the smallest integer such that fact[H]/(fact[H-H′]*fact[H′]) is at least K+2, wherein fact is the factorial operator, wherein H′ is the smallest integer that is at least H/2. 25. The method of claim 19, wherein each pre-coding relation in the second set of pre-coding relations is uniquely associated with an intermediate symbol in the third set of intermediate symbols and is associated with a specified set of intermediate symbols among the first set and second set of intermediate symbols, wherein the pre-coding relation is a linear constraint on the associated intermediate symbol and the intermediate symbols in the specified set. 26. The method of claim 25, wherein the linear constraint is an exclusive-or constraint. 27. The method of claim 25, wherein each of the intermediate symbols in the first set or the second set of intermediate symbols is in the specified set of approximately one-half of the pre-coding relations in the second set of pre-coding relations. 28. The method of claim 25, wherein for each first intermediate symbol in the first set or second set of intermediate symbols and for each second intermediate symbol in the first set or second set of intermediate symbols that is the next consecutive intermediate symbol following the first intermediate symbol, the symmetric difference of pre-coding relations in the second set of pre-coding relations of which the first intermediate symbol is a member of the specified set and of which the second intermediate symbol is a member of the specified set is exactly two. 29. A method of decoding encoded data received over a communications channel transmitted from a source to a destination, the method comprising: receiving a predetermined number, N, of symbols, wherein the received symbols comprise a combination of received source symbols and received repair symbols generated from a plurality of an ordered set of K source symbols,generating to a desired degree of accuracy one or more unreceived source symbols of the ordered set of K source symbols,wherein each received symbol has an associated symbol relation that is determined by a systematic index, J(K), where J(K) is determined by K,wherein the value of each unreceived source symbol is determined by the associated symbol relation and a plurality of L intermediate symbol values, wherein L is at least K,wherein the L intermediate symbol values are determined by the K source symbol values and by the K symbol relations associated with the K source symbols and by a set of L-K pre-coding relations,wherein the L intermediate symbol values can be generated to a desired degree of accuracy from the N received source and repair symbols. 30. The method of claim 29, further comprising precalculating and storing the systematic index J(K) in a table for each relevant value of K. 31. The method of claim 29, wherein the systematic index J(K) is equal to 18, 14, 43, 55, 41, 88, 213, 415, and 2665 for values of K equal to 4, 8, 16, 64, 128, 512, 1024, 4096, and 8192, respectively. 32. The method of claim 29, wherein the symbol relations impose linear constraints on sets of received source symbols. 33. The method of claim 32, wherein the linear constraints are exclusive-or constraints. 34. The method of claim 29, wherein each source symbol has an associated encoding symbol identifier (“ESI”) that identifies the source symbol, wherein the systematic index J(K) and a value X, wherein X is a valid ESI, determines the symbol relation for the source symbol identified by ESI X. 35. The method of claim 34, wherein the systematic index J(K) and the ESI X can be used to generate a triple (a[X],b[X],d[X]) that defines the symbol relation for the source symbol identified by ESI X. 36. The method of claim 34, wherein each source symbol can be identified by an integer ESI in the range 0 to K−1, inclusive. 37. The method of claim 34, wherein each repair symbol can be identified by an integer ESI that is at least K. 38. The method of claim 35, wherein the triple (a[X],b[X],d[X]) that defines the source symbol relation associated with the source symbol with ESI X places the following linear constraint on the value C′ [X] for source symbol with ESI X and the values C[0], C[1], . . . , C[L−1] of the L intermediate symbols: defining an array of positive integer values B[0], . . . , B[J−1], wherein J is the minimum of d[X] and L, wherein L′ is the smallest integer that is prime that is at least the value of L, and wherein the values of the array of positive integer values B[0], . . . , B[J−1] are set using the method comprising: (a) setting the initial value of B[0] to b[X];while B[0] is at least L, recalculating B[0] as the previous value of B[0] plus a[X] modulo L′;(c) for values of j starting at 1 and going up to J−1 in increments of one,(d), initializing the value of B[j] to B[j−1] plus a[X]; and(e) while B[j] is at least L, recalculating B[j] as the previous value of B[j] plus a[X] modulo L′. 39. The method of claim 35, wherein the generation of the triple (a[X],b[X],d[X]) from an ESI X comprises the following steps: calculating a value A as (53591+J(K)*997) % 65521, wherein * is the multiplication operator and % is the modulo operator;calculating a value B as 10267*(J(K)+1) % 65521;calculating a value Y as (B+X*A) % 65521; anddetermining a value v, wherein v is in the range from 0 and 1048575, inclusive, where v is calculated as the output of a random generator applied to the inputs Y, 0, and 1048575. 40. The method of claim 39 further comprising: determining d[X] based on a degree function applied to the input v. 41. The method of claim 39 further comprising: determining a[X], wherein a[X] is in the range between 0 and L′−1, inclusive, wherein L′ is the smallest prime number greater than or equal to L, wherein L′ is calculated as one plus the output of the random generator applied to the inputs Y, 1 and L′−1. 42. The method of claim 39 further comprising: determining b[X], wherein b[X] is in the range between 0 and L′, inclusive, wherein b[X] is calculated as the output of the random generator applied to the input Y, 2 and L′. 43. The method of claim 39, wherein the value of d[X] is determined based on v as follows: if the value of v is between 0 and 10240, inclusive, then the value of d[X] is 1,if the value of v is between 10241 and 4911581, inclusive, then the value of d[X] is 2,if the value of v is between 4911582 and 712793, inclusive, then the value of d[X] is 3,if the value of v is between 712794 and 831694, inclusive, then the value of d[X] is 4,if the value of v is between 831695 and 948445, inclusive, then the value of d[X] is 10,if the value of v is between 948446 and 1032188, inclusive, then the value of d[X] is 11,if the value of v is between 1032189 and 1048575, inclusive, then the value of d[X] is 40. 44. The method of claim 39, wherein the random generator on inputs Y, i, and m is calculated as (V0[(Y+i) % 256]^(V1[(floor(Y/256)+i) % 256]) % m, where % is the modulo operator, ^ is the exclusive-or operator, / is the division operator, floor calculates the largest integer that is at most the input value, and V0 and V1 are each tables of 256 integers chosen randomly or pseudo-randomly. 45. The method of claim 44, wherein table V0 has values, in decimal representation, of 3067016507, 689605112, 4005368743, 4048876515, 778296777, 2669179716, 3457502702, 4291353919, 2687243553, 2068983570, 616452097, 3272161958, 234652930, 179350258, 2054995199, and 1358307511 for table indices of 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, and 256, respectively, when a first entry of table V0 has a table index of 1. 46. The method of claim 44, wherein table V1 has values, in decimal representation, of 4114760273, 3302235057, 640417429, 852173610, 4071072948, 3904109414, 3123492423, 3870972145, 2712821515, 4267074718, 4259411376, 1351086955, 4187322100, 2822905141, 3762994475, and 4135048896 for table indices of 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, and 256, respectively, when a first entry of table V1 has a table index of 1. 47. The method of claim 29, wherein the number L-K of pre-coding relations comprises a first set of S pre-coding relations and a second set of H pre-coding relations, and wherein the L intermediate symbols comprises a first set of K intermediate symbols, a second set of S intermediate symbols, and a third set of H intermediate symbols. 48. The method of claim 47, wherein each pre-coding relation in the first set of pre-coding relations is uniquely associated with an intermediate symbol in the second set of intermediate symbols and is associated with a specified set of intermediate symbols among the first set of intermediate symbols, wherein each pre-coding relation is a linear constraint on the value of the associated intermediate symbol and the values of the intermediate symbols in the specified set. 49. The method of claim 48, wherein the linear constraint is an exclusive-or constraint. 50. The method of claim 48, wherein for each first pre-coding relation among the first set of pre-coding relations and for each second pre-coding relation among the first set of pre-coding relations, the number of intermediate symbols that are both in the specified set associated with the first pre-coding relation and in the specified set associated with the second pre-coding relation is at most 3. 51. The method of claim 48, wherein each of the intermediate symbols in the first set of intermediate symbols is in the specified set of exactly three of the pre-coding relations in the first set of pre-coding relations. 52. The method of claim 47, wherein S is the smallest prime integer that is at least as large as 0.01*K+X, wherein X is the smallest positive integer such that X*(X−1) is at least 2*K,wherein H is the smallest integer such that fact[H]/(fact[H-H]*fact[H′]) is at least K+2, wherein fact is the factorial operator, wherein H′ is the smallest integer that is at least H/2. 53. The method of claim 47, wherein each pre-coding relation in the second set of pre-coding relations is uniquely associated with an intermediate symbol in the third set of intermediate symbols and is associated with a specified set of intermediate symbols among the first set and second set of intermediate symbols, wherein the pre-coding relation is a linear constraint on the associated intermediate symbol and the intermediate symbols in the specified set. 54. The method of claim 53, wherein the linear constraint is an exclusive-or constraint. 55. The method of claim 53, wherein each of the intermediate symbols in the first set or the second set of intermediate symbols is in the specified set of approximately one-half of the pre-coding relations in the second set of pre-coding relations. 56. The method of claim 53, wherein for each first intermediate symbol in the first set or second set of intermediate symbols and for each second intermediate symbol in the first set or second set of intermediate symbols that is the next consecutive intermediate symbol following the first intermediate symbol, the symmetric difference of pre-coding relations in the second set of pre-coding relations of which the first intermediate symbol is a member of the specified set and of which the second intermediate symbol is a member of the specified set is exactly two. 57. The method of claim 1, wherein the output symbols are placed into one or more packets for transmission. 58. The method of claim 29, wherein more than one received symbol received in at least one packet. 59. The method of claim 6, wherein the output symbols are placed into packets for transmission, wherein each output symbol has an associated ESI, and wherein an ESI is included in each packet to identify a first output symbol placed into the packet. 60. The method of claim 59, wherein more than one output symbol is placed into at least one packet and for packets that carry more than one output symbol, the ESIs for the second and subsequent output symbols placed in the packet are determined by the ESI for the first output symbol placed in the packet. 61. The method of claim 60, wherein the ESI determined for the second output symbol placed in a packet is one greater than the ESI placed in the packet that is associated with the first output symbol placed in the packet. 62. The method of claim 34, wherein the output symbols are received in one or more packets, wherein each output symbol has an associated ESI, and wherein an ESI is received in each packet to identify a first output symbol in the packet. 63. The method of claim 62, wherein more than one output symbol is received in at least one packet, wherein the ESIs for the second and subsequent output symbols received in packets with more than one output symbol are determined by the ESI for the first output symbol in the packet. 64. The method of claim 63, wherein the ESI determined for the second output symbol in a received packet is one greater than the ESI in the packet that is associated with the first output symbol in the packet. 65. The method of claim 1 wherein the K source symbols correspond to a source block, wherein the source block is divided into N′ sub-blocks, wherein each of the N′ sub-blocks is composed of K′ sub-symbols, wherein one or more source blocks can correspond to a source file, wherein each of the one or more source blocks are encoded separately from the other source blocks. 66. The method of claim 65 wherein the source file is partitioned into one or more source blocks of approximately equal size as a function of the number of source symbols per source blocks and the number of source blocks, and wherein each source block is partitioned into one or more sub-blocks of approximately equal size as a function of the size of a source symbol and the number of sub-blocks per source block. 67. The method of claim 66 wherein more than one output symbol is placed into a packet that is used for transmission. 68. The method of claim 66 wherein one or more parameters used to partition the source file into one or more source blocks and used to partition the one or more source blocks into one or more subblocks are made known at the destination of the output symbols. 69. The method of claim 1 wherein the K source symbols correspond to a source block, wherein the source block is defined by a transport protocol for streaming data. 70. The method of claim 69 wherein one or more parameters used to determine how the K source symbols correspond to the source block are made known at the destination of the output symbols. 71. The method of claim 69 wherein more than one output symbol is placed into a packet that is used for transmission. 72. The method of claim 29 wherein the K source symbols correspond to a source block, wherein the source block is defined by a transport protocol for streaming data. 73. The method of claim 72 wherein one or more parameters used to determine how the K source symbols correspond to the source block are made known at the destination of the output symbols. 74. The method of claim 72 wherein more than one output symbol is received in a received packet.
Copyright KISTI. All Rights Reserved.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.