# US 9,521,084 B2 · Network coding method, relay apparatus, and selection apparatus > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,521,084 B2 - Document ID: US9521084B2 - Status: Granted - Kind: B2 - Application number: 14/451,691 - Filed: 2014-08-05 - Published: 2014-11-20 - Granted: 2016-12-13 - Earliest claimed: 2012-02-10 - Assignees: Huawei Technologies Co., Ltd. - Applicants: Huawei Technologies Co., Ltd. - Inventors: Lili Wei; Wen Chen; Yuejun Wei; Ying Jin - Web page: https://patentgrep.com/patent/US9521084B2 ## CPC - H04L 47/38: by adapting coding or compression rate - H04B 7/15521: {combining by calculations packets received from different stations before transmitting the combined packets as part of network coding (network coding aspects for detection or prevention of errors in the information received H04L1/0076; network traffic management with optimizing of information sizing, e.g. header compression, by using assembly and disassembly of packets H04W28/065)} - H04L 1/0002: {by adapting the transmission rate} - H04L 47/25: with rate being modified by the source upon detecting a change of network conditions - H04L 2001/0097: {Relays} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - H04B: TRANSMISSION ## Abstract Embodiments of the present invention relate to the field of communications, and provide a network coding method, a relay apparatus and a selection apparatus, which can avoid a case that a network coding system matrix is not full rank, and improve correctness of decoding. The network coding method includes: obtaining network coding information, where the network coding information includes information of a candidate network coding vector set and a candidate transmission rate set, and transmission rates in the candidate transmission rate set are in one-to-one correspondence with network coding vectors in the candidate network coding vector set; selecting a full rank network matrix according to the network coding information; and coding received source node information according to the full rank network matrix. The network coding method, relay apparatus and selection apparatus provided in the embodiments of the present invention are used for network coding. ## Claims ### Claim 1 A network coding method, comprising: obtaining network coding information, wherein the network coding information comprises information of a candidate network coding vector set and a candidate transmission rate set, and transmission rates in the candidate transmission rate set are in one-to-one correspondence with network coding vectors in the candidate network coding vector set; selecting a full rank network matrix according to the network coding information; and coding information received from a source node according to the full rank network matrix; wherein obtaining network coding information comprises: obtaining a non-zero integer vector to be used for selection of the candidate network coding vector set; selecting a vector a satisfying aTGa≦C from the integer vector, to form a vector set M and a corresponding rate set N, wherein C is a constant; a matrix G satisfies a formula G = I - P ⁡ ( h ⁢ ⁢ h T ) 1 + P ⁢  h  2 , wherein I is a unit matrix, P is transmit signal power h is a channel vector from a source apparatus to a relay apparatus, and ∥h∥2 is a square of a modulus of a vector h; and aT is transposition of the vector a; when the number of vectors in the vector set M is greater than or equal to a preset number t, sorting transmission rates in the rate set N in descending order, and selecting first tth transmission rates that are relatively great, to form the candidate transmission rate set; and selecting, from the vector set M, vectors corresponding to the first tth transmission rates that are relatively great, to form the candidate network coding vector set. ### Claim 2 (depends on 1) The method according to claim 1, wherein selecting a vector a satisfying aTGa≦C from the integer vector, to form a vector set M comprises: obtaining a vector b corresponding to a minimum characteristic value of the matrix G; replacing a numeral greater than 0 in the vector b with +1, and replacing a numeral smaller than 0 with −1, to obtain an integer vector c; and based on C=cTGc , selecting the vector a satisfying aTGa≦C from the integer vector, to form the vector set M. ### Claim 3 (depends on 1) The method according to claim 1, further comprising: when the number of the vectors in the vector set M is smaller than the preset number t, increasing a value of the constant C. ### Claim 4 (depends on 3) The method according to claim 3, wherein increasing the value of the constant C is doubling the constant C. ### Claim 5 A network coding method, comprising: obtaining network coding information, wherein the network coding information comprises information of a candidate network coding vector set and a candidate transmission rate set, and transmission rates in the candidate transmission rate set are in one-to-one correspondence with network coding vectors in the candidate network coding vector set; selecting a full rank network matrix according to the network coding information; and coding information received from a source node according to the full rank network matrix; wherein selecting a full rank network matrix according to the network coding information comprises: sorting all transmission rates in the candidate transmission rate set in descending order, to obtain a test rate set; when the number of the relay apparatuses is n, using the nth transmission rate in the test rate set as a test rate; selecting one network coding vector from each candidate network coding vector set corresponding to the relay apparatus, to form a test coding vector matrix, wherein a transmission rate corresponding to the selected network coding vector is greater than or equal to the test rate; and when the test coding vector matrix is a full rank matrix, determining that the test coding vector matrix is a full rank network matrix. ### Claim 6 A network coding method, comprising: obtaining network coding information, wherein the network coding information comprises information of a candidate network coding vector set and a candidate transmission rate set, and transmission rates in the candidate transmission rate set are in one-to-one correspondence with network coding vectors in the candidate network coding vector set; selecting a full rank network matrix according to the network coding information; and coding information received from a source node according to the full rank network matrix; wherein selecting a full rank network matrix according to the network coding information comprises: sorting all transmission rates in the candidate transmission rate set in descending order, to obtain a test rate set; when the number of the relay apparatuses is n, using the nth transmission rate in the test rate set as a test rate; selecting one network coding vector from each candidate network coding vector set corresponding to the relay apparatus, wherein a transmission rate corresponding to the selected network coding vector is greater than or equal to the test rate; and when a test coding vector matrix cannot be formed according to the selected network coding vector, or a test coding vector matrix formed according to the selected network coding vector is not a full rank matrix, sequentially using a transmission rate next to the current test rate in the test rate set as a new test rate, and repeating step c until it is determined that the test coding vector matrix is a full rank matrix. ### Claim 7 A network coding method, comprising: receiving network coding information sent by a relay apparatus, wherein the network coding information comprises information of a candidate network coding vector set and a candidate transmission rate set, and transmission rates in the candidate transmission rate set are in one-to-one correspondence with network coding vectors in the candidate network coding vector set; selecting a full rank network matrix according to the network coding information; and sending the full rank network matrix to the relay apparatus, wherein the relay apparatus codes information received from a source node according to the full rank network matrix; wherein selecting a full rank network matrix according to the network coding information comprises: sorting all transmission rates in the candidate transmission rate set in descending order, to obtain a test rate set; when the number of the relay apparatuses is n, using the nth transmission rate in the test rate set as a test rate; selecting one network coding vector from each candidate network coding vector set corresponding to the relay apparatus, to form a test coding vector matrix, wherein a transmission rate corresponding to the selected network coding vector is greater than or equal to the test rate; and when the test coding vector matrix is a full rank matrix, determining that the test coding vector matrix is a full rank network matrix. ### Claim 8 A network coding method, comprising: receiving network coding information sent by a relay apparatus, wherein the network coding information comprises information of a candidate network coding vector set and a candidate transmission rate set, and transmission rates in the candidate transmission rate set are in one-to-one correspondence with network coding vectors in the candidate network coding vector set; selecting a full rank network matrix according to the network coding information; and sending the full rank network matrix to the relay apparatus, wherein the relay apparatus codes information received from a source node according to the full rank network matrix; wherein selecting a full rank network matrix according to the network coding information comprises: sorting all transmission rates in the candidate transmission rate set in descending order, to obtain a test rate set; when the number of the relay apparatuses is n, using the nth transmission rate in the test rate set as a test rate; selecting one network coding vector from each candidate network coding vector set corresponding to the relay apparatus, wherein a transmission rate corresponding to the selected network coding vector is greater than or equal to the test rate; and when a test coding vector matrix cannot be formed according to the selected network coding vector, or a test coding vector matrix formed according to the selected network coding vector is not a full rank matrix, sequentially using a transmission rate next to the current test rate in the test rate set as a new test rate, and repeating step c until it is determined that the test coding vector matrix is a full rank network matrix. ### Claim 9 A relay apparatus, comprising: a processor; and memory coupled to the processor, the memory comprising instructions that, when executed by the processor, cause the relay apparatus to: obtain network coding information, wherein the network coding information comprises information of a candidate network coding vector set and a candidate transmission rate set, and transmission rates in the candidate transmission rate set are in one-to-one correspondence with network coding vectors in the candidate network coding vector set; select a full rank network matrix according to the network coding information; code information received from a source node according to the full rank network matrix; obtain all non-zero integer vectors to be used for selection of the candidate network coding vector set; select a vector a satisfying aTGa≦C from the integer vectors, to form a vector set M and a corresponding rate set N, wherein C is a constant; a matrix G satisfies a formula G = I - P ⁡ ( hh T ) 1 + P ⁢  h  2 , 10 wherein I is a unit matrix, P is transmit signal power, h is a channel vector from a source apparatus to the relay apparatus, and ∥h∥2 is a square of a modulus of a vector h; and aT is transposition of the vector a; when the number of vectors in the vector set M is greater than or equal to a preset number t, sort transmission rates in the rate set N in descending order, and select first tth transmission rates that are relatively great, to form the candidate transmission rate set; and select, from the vector set M, vectors corresponding to the first tth transmission rates that are relatively great, to form the candidate network coding vector set. ### Claim 10 (depends on 9) The apparatus according to claim 9, wherein the memory comprises instructions that, when executed by the processor, cause the relay apparatus to: when the number of the vectors in the vector set M is smaller than the preset number t, increase a value of the constant C. ### Claim 11 (depends on 10) The apparatus according to claim 10, wherein increasing a value of the constant C is doubling the constant C. ### Claim 12 A relay apparatus, comprising: a processor; and memory coupled to the processor, the memory comprising instructions that, when executed by the processor, cause the relay apparatus to: obtain network coding information, wherein the network coding information comprises information of a candidate network coding vector set and a candidate transmission rate set, and transmission rates in the candidate transmission rate set are in one-to-one correspondence with network coding vectors in the candidate network coding vector set; select a full rank network matrix according to the network coding information; code information received from a source node according to the full rank network matrix; sort all transmission rates in the candidate transmission rate set in descending order, to obtain a test rate set; when the number of the relay apparatuses is n, use the nth transmission rate in the test rate set as a test rate; select one network coding vector from each candidate network coding vector set corresponding to the relay apparatus, to form a test coding vector matrix, wherein a transmission rate corresponding to the selected network coding vector is greater than or equal to the test rate; and when the test coding vector matrix is a full rank matrix, determine that the test coding vector matrix is a full rank network matrix. ### Claim 13 A relay apparatus, comprising: a processor; and memory coupled to the processor, the memory comprising instructions that, when executed by the processor, cause the relay apparatus to: obtain network coding information, wherein the network coding information comprises information of a candidate network coding vector set and a candidate transmission rate set, and transmission rates in the candidate transmission rate set are in one-to-one correspondence with network coding vectors in the candidate network coding vector set; select a full rank network matrix according to the network coding information; code information received from a source node according to the full rank network matrix; sort all transmission rates in the candidate transmission rate set in descending order, to obtain a test rate set; when the number of the relay apparatuses is n, use the nth transmission rate in the test rate set as a test rate; select one network coding vector from each candidate network coding vector set corresponding to the relay apparatus, wherein a transmission rate corresponding to the selected network coding vector is greater than or equal to the test rate; and when a test coding vector matrix cannot be formed according to the selected network coding vector, or a test coding vector matrix formed according to the selected network coding vector is not a full rank matrix, sequentially use a transmission rate next to the current test rate in the test rate set as a new test rate, and repeat step c until it is determined that the test coding vector matrix is a full rank matrix. ### Claim 14 A selection apparatus, comprising: a processor; and memory coupled to the processor, the memory comprising instructions that, when executed by the processor, cause the selection apparatus to: receive network coding information sent by a relay apparatus, wherein the network coding information comprises information of a candidate network coding vector set and a candidate transmission rate set, and transmission rates in the candidate transmission rate set are in one-to-one correspondence with network coding vectors in the candidate network coding vector set; select a full rank network matrix according to the network coding information; sort all transmission rates in the candidate transmission rate set in descending order, to obtain a test rate set; when the number of the relay apparatuses is n, use the nth transmission rate in the test rate set as a test rate; select one network coding vector from each candidate network coding vector set corresponding to the relay apparatus, to form a test coding vector matrix, wherein a transmission rate corresponding to the selected network coding vector is greater than or equal to the test rate; and when the test coding vector matrix is a full rank matrix, determine that the test coding vector matrix is a full rank network matrix; and a transmitter that sends the full rank network matrix to the relay apparatus, so that the relay apparatus codes information received from a source node according to the full rank network matrix. ### Claim 15 A selection apparatus, comprising: a processor; and memory coupled to the processor, the memory comprising instructions that, when executed by the processor, cause the selection apparatus to: receive network coding information sent by a relay apparatus, wherein the network coding information comprises information of a candidate network coding vector set and a candidate transmission rate set, and transmission rates in the candidate transmission rate set are in one-to-one correspondence with network coding vectors in the candidate network coding vector set; select a full rank network matrix according to the network coding information; sort all transmission rates in the candidate transmission rate set in descending order, to obtain a test rate set; when the number of the relay apparatuses is n, use the nth transmission rate in the test rate set as a test rate; select one network coding vector from each candidate network coding vector set corresponding to the relay apparatus, wherein a transmission rate corresponding to the selected network coding vector is greater than or equal to the test rate; and when a test coding vector matrix cannot be formed according to the selected network coding vector, or a test coding vector matrix formed according to the selected network coding vector is not a full rank matrix, sequentially use a transmission rate next to the current test rate in the test rate set as a new test rate, and repeat step c until it is determined that the test coding vector matrix is a full rank network matrix; and a transmitter that sends the full rank network matrix to the relay apparatus, so that the relay apparatus codes information received from a source node according to the full rank network matrix.