System and method for providing h-arq rate compatible codes for high throughput applications

Abstract

In one embodiment, the present patent application comprises a method and apparatus to generate low rate protographs from high rate protographs, comprising copying a base graph; permuting end points of edges of a same type in copies of the base graph to produce a permuted graph; and pruning systematic input nodes in the permuted graph and the edges connected to them. In another embodiment, the present patent application comprises a method and apparatus to generate high-rate codes from low-rate codes, comprising puncturing a subset of codeword bits, wherein the step of puncturing a subset of codeword bits comprises regular-irregular puncturing the subset of codeword bits, random puncturing variable nodes, or progressive node puncturing variable nodes to obtain a desired code from a preceding code.

1 . A method of generating high-rate codes from low-rate codes, comprising: puncturing a subset of codeword bits. 
     
     
         2 . The method of generating high-rate codes from low-rate codes according to  claim 1 , wherein said low-rate codes are parent codes. 
     
     
         3 . The method of generating high-rate codes from low-rate codes according to  claim 1 , wherein said step of puncturing a subset of codeword bits comprises regular-irregular puncturing said subset of codeword bits, comprising:
 choosing a parent code with a desired base rate;   finding a set of non-punctured variable nodes in a preceding code for each rate in a set of desired rates;   calculating a number of variable nodes to be punctured to go from a preceding rate to a desired rate;   calculating alpha and beta such that a puncturing pattern on a non-punctured set is regular; and   puncturing a pattern which is a function said alpha and said beta on said non-punctured set.   
     
     
         4 . The method of generating high-rate codes from low-rate codes according to  claim 1 , wherein said step of puncturing a subset of codeword bits comprises random puncturing variable nodes. 
     
     
         5 . The method of generating high-rate codes from low-rate codes according to  claim 1 , wherein said step of puncturing a subset of codeword bits comprises:
 progressive node puncturing variable nodes to obtain a desired code from a preceding code.   
     
     
         6 . The method of generating high-rate codes from low-rate codes according to  claim 2 , wherein said parent codes are generated by:
 copying a base graph;   permuting end points of edges of a same type in copies of said base graph to produce a permuted graph; and   pruning systematic input nodes in said permuted graph and said edges connected to them.   
     
     
         7 . The method of generating high-rate codes from low-rate codes according to  claim 3 , wherein said step of calculating a number of variable nodes to be punctured to go from a preceding rate to a desired rate uses the following formula:
     pm =Floor( N −( N−C )/ Rm−N   —   tm− 1),
   
       where pm is the number of variable nodes to be punctured, Rm is the desired rate, Rm−1 is a preceding rate, N and C are a number of variable nodes and check nodes in a lifted graph respectively, N_tm−1 is a total number of said punctured variable nodes in the lifted graph corresponding to a preceding code C{Rm−1}, and Floor ( ) represents a floor function. 
     
     
         8 . The method of generating high-rate codes from low-rate codes according to  claim 3 , wherein said step of calculating alpha and beta such that a puncturing pattern on the non-punctured set is regular uses the following formulas:
   alpha=Floor[( rm− 1 −pm )/( pm− 1)] and     beta= rm− 1−alpha( pm− 1)− pm,  
   
       where pm is the number of variable nodes to be punctured, rm−1 is a cardinality of the set of non-punctured redundancy variable nodes in preceding code C{Rm−1}, Rm−1 is a preceding rate, and Floor ( ) represents a floor function. 
     
     
         9 . The method of generating high-rate codes from low-rate codes according to  claim 3 , wherein said step of puncturing a pattern which is a function said alpha and said beta on said non-punctured set comprises using a pattern [N1 {alpha nodes} N2 {alpha nodes} . . . Nm {beta nodes}], where N1, N2, . . . Np_m are the indices of the punctured variable nodes within the set of non-punctured redundancy nodes of cardinality rm−1. 
     
     
         10 . The method of generating high-rate codes from low-rate codes according to  claim 4 , further comprising randomly searching said subset of codeword bits, comprising:
 i) choosing a parent code with a desired base rate;   ii) initializing a signal-to-noise ratio for each desired rate in the set of desired rates;   iii) finding a set of non-punctured variable nodes in a preceding code with a preceding rate;   iv) calculating a number of variable nodes to be punctured to go from said preceding rate to a desired rate;   v) randomly choosing said number of variable nodes to be punctured from said set of non-punctured variable nodes;   vi) constructing a code from the preceding rate by puncturing said chosen number of variable nodes;   vii) running density evolution to test if said constructed code achieves a negligible error with the initialized signal-to-noise ratio;   viii) iteratively searching for a new signal-to-noise threshold of said constructed code, setting said constructed code as a winner code and setting said signal-to-noise ratio equal to a new threshold if said constructed code achieves a negligible error with said signal-to-noise ratio; and   ix) repeating said random searching by repeating steps v through vii if said constructed code does not achieve a negligible error with said signal-to-noise ratio.   
     
     
         11 . The method of generating high-rate codes from low-rate codes according to  claim 5 , wherein said step of progressive node puncturing variable nodes to obtain a desired code from a preceding code comprises:
 progressively puncturing said variable nodes from a set of non-punctured said variable nodes of cardinality rm−1, wherein rm−1, is a number of members in the set of non-punctured redundancy variable nodes in a preceding code and wherein non-punctured redundant variable nodes of the preceding code may be punctured to yield the code of a desired rate.   
     
     
         12 . The method of generating high-rate codes from low-rate codes according to  claim 10 , wherein said step of iteratively searching for a new threshold of said constructed code comprises:
 a) iteratively bisecting said range to select a test signal-to-noise ratio;   b) determining if said test signal-to-noise ratio achieves zero error; and   c) repeating steps a and b until a desired accuracy in said signal-to-noise ratio is achieved.   
     
     
         13 . The method of generating high-rate codes from low-rate codes according to  claim 11 , wherein said step of progressively puncturing variable nodes from a set of non-punctured said variable nodes, comprises a step of initializing by:
 calculating for each check node connected to at least one said variable node a number of said punctured variable nodes connected to said check nodes, wherein each of said check nodes is connected to only one said punctured variable node;   finding said set of said non-punctured variable nodes;   calculating for each said non-punctured variable node a number of said check nodes connected to each said non-punctured variable node, wherein each of said check nodes are connected to only one said punctured variable node; and   calculating for each said non-punctured variable node a sum of said punctured variable nodes connected to said check nodes, wherein said check nodes are connected to said non-punctured variable nodes.   
     
     
         14 . The method of generating high-rate codes from low-rate codes according to  claim 13 , wherein said step of progressively puncturing variable nodes from a set of non-punctured said variable nodes, further comprises a step of puncturing by finding said punctured variable node while a number of said punctured variable nodes at this step is less than a number of said punctured variable nodes for said desired rate. 
     
     
         15 . The method of generating high-rate codes from low-rate codes according to  claim 14 , wherein said step of finding said punctured variable node while a number of said punctured variable nodes at this step is less than a number of said punctured variable nodes for said desired rate comprises:
 a) finding a second set of said non-punctured variable nodes in said set of said non-punctured variable nodes for which a number of neighboring of said check nodes is a minimum;   b) setting the punctured variable node to be the node in the second set if said number of said non-punctured variable nodes in said second set of step a is 1;   c) execute steps ci-civ if the number of said non-punctured variable nodes of said second set of step a is >1;   ci) finding a subset of said second set of said non-punctured variable nodes from step a, in which the sum of said number of punctured variable nodes connected to said check nodes which are connected to said non-punctured variable nodes is a minimum;   cii) setting said punctured variable nodes to the single node in the subset of step ci if said number of said nonpunctured variable nodes in said subset of step ci is 1;   ciii) choosing said variable nodes from said non-punctured variable nodes in the subset from step ci at random if the number of the non-punctured variable nodes found in the subset from step ci is greater than 1; and   civ) puncturing said chosen variable node and removing said punctured, chosen variable node from the set of non-punctured variable nodes.   
     
     
         16 . The method of generating high-rate codes from low-rate codes according to  claim 15 , wherein said step of progressively puncturing variable nodes from a set of non-punctured said variable nodes, further comprises a step of updating, comprising:
 updating said number of punctured variable nodes connected to the check nodes for each of said check nodes neighboring said punctured variable nodes;   updating the number of said check nodes connected to said non-punctured variable nodes, wherein said check node is connected to only one said punctured variable node for each said variable node neighboring said check node; and   updating the sum of said punctured variable nodes connected to said check node, where said check node is connected to said non-punctured variable nodes for each said variable node neighboring said check node.   
     
     
         17 . The method of generating high-rate codes from low-rate codes according to  claim 16 , wherein said step of progressively puncturing variable nodes from a set of non-punctured said variable nodes, further comprises a step of maximizing a connectivity between the check nodes with only one punctured variable node and the other punctured variable nodes. 
     
     
         18 . The method of generating high-rate codes from low-rate codes according to  claim 17 , wherein said step of maximizing a connectivity between the check nodes with only one punctured variable node and the other punctured variable nodes, comprises:
 initializing a puncturing score to zero;   changing a random seed;   running said steps of  claims 5 ,  11 ,  13 ,  14 , and  15  on said preceding code to get said desired punctured code;   calculating the puncturing score of the desired punctured code; and   choosing the puncturing pattern with the largest puncturing score if the puncturing score of the desired punctured code is greater than the puncturing score of the preceding code.   
     
     
         19 . A means for generating high-rate codes from low-rate codes, comprising:
 means for puncturing a subset of codeword bits.   
     
     
         20 . The means for generating high-rate codes from low-rate codes according to  claim 19 , wherein said low-rate codes are parent codes. 
     
     
         21 . The means for generating high-rate codes from low-rate codes according to  claim 19 , wherein said means for puncturing a subset of codeword bits comprises means for regular-irregular puncturing said subset of codeword bits, comprising:
 means for choosing a parent code with a desired base rate;   means for finding a set of non-punctured variable nodes in a preceding code for each rate in a set of desired rates;   means for calculating a number of variable nodes to be punctured to go from a preceding rate to a desired rate;   means for calculating alpha and beta such that a puncturing pattern on a non-punctured set is regular; and   means for puncturing a pattern which is a function said alpha and said beta on said non-punctured set.   
     
     
         22 . The means for generating high-rate codes from low-rate codes according to  claim 19 , wherein said means for puncturing a subset of codeword bits comprises means for random puncturing variable nodes. 
     
     
         23 . The means for generating high-rate codes from low-rate codes according to  claim 19 , wherein said means for puncturing a subset of codeword bits comprises:
 means for progressive node puncturing variable nodes to obtain a desired code from a preceding code.   
     
     
         24 . The means for generating high-rate codes from low-rate codes according to  claim 20 , wherein said parent codes are generated by:
 means for copying a base graph;   means for permuting end points of edges of a same type in copies of said base graph to produce a permuted graph; and   means for pruning systematic input nodes in said permuted graph and said edges connected to them.   
     
     
         25 . The means for generating high-rate codes from low-rate codes according to  claim 21 , wherein said means for calculating a number of variable nodes to be punctured to go from a preceding rate to a desired rate uses the following formula:
     pm =Floor( N −( N−C )/ Rm−N   —   tm− 1),
   
       where pm is the number of variable nodes to be punctured, Rm is the desired rate, Rm−1 is a preceding rate, N and C are a number of variable nodes and check nodes in a lifted graph respectively, N_tm−1 is a total number of said punctured variable nodes in the lifted graph corresponding to a preceding code C{Rm−1}, and Floor ( ) represents a floor function. 
     
     
         26 . The means for generating high-rate codes from low-rate codes according to  claim 21 , wherein said means for calculating alpha and beta such that a puncturing pattern on the non-punctured set is regular uses the following formulas:
   alpha=Floor[( rm− 1 −pm )/( pm− 1)]; and     beta= rm− 1−alpha( pm− 1)− pm,  
   
       where pm is the number of variable nodes to be punctured, rm−1 is a cardinality of the set of non-punctured redundancy variable nodes in preceding code C{Rm−1}, Rm−1 is a preceding rate, and Floor ( ) represents a floor function. 
     
     
         27 . The means for generating high-rate codes from low-rate codes according to  claim 21 , wherein said means for puncturing a pattern which is a function said alpha and said beta on said non-punctured set comprises means for using a pattern [N1 {alpha nodes} N2 {alpha nodes} . . . Nm {beta nodes}], where N1, N2, . . . Np_m are the indices of the punctured variable nodes within the set of non-punctured redundancy nodes of cardinality rm−1. 
     
     
         28 . The means for generating high-rate codes from low-rate codes according to  claim 22 , further comprising means for randomly searching said subset of codeword bits, comprising:
 i) means for choosing a parent code with a desired base rate;   ii) means for initializing a signal-to-noise ratio for each desired rate in the set of desired rates;   iii) means for finding a set of non-punctured variable nodes in a preceding code with a preceding rate;   iv) means for calculating a number of variable nodes to be punctured to go from said preceding rate to a desired rate;   v) means for randomly choosing said number of variable nodes to be punctured from said set of non-punctured variable nodes;   vi) means for constructing a code from the preceding rate by puncturing said chosen number of variable nodes;   vii) means for running density evolution to test if said constructed code achieves a negligible error with the initialized signal-to-noise ratio;   viii) means for iteratively searching for a new signal-to-noise threshold of said constructed code, setting said constructed code as a winner code and setting said signal-to-noise ratio equal to a new threshold if said constructed code achieves a negligible error with said signal-to-noise ratio; and   ix) means for repeating said random searching by repeating steps v through vii if said constructed code does not achieve a negligible error with said signal-to-noise ratio.   
     
     
         29 . The means for generating high-rate codes from low-rate codes according to  claim 23 , wherein said means for progressive node puncturing variable nodes to obtain a desired code from a preceding code comprises:
 means for progressively puncturing said variable nodes from a set of non-punctured said variable nodes of cardinality rm−1, wherein rm−1, is a number of members in the set of non-punctured redundancy variable nodes in a preceding code and wherein non-punctured redundant variable nodes of the preceding code may be punctured to yield the code of a desired rate.   
     
     
         30 . The means for generating high-rate codes from low-rate codes according to  claim 28 , wherein said means for iteratively searching for a new threshold of said constructed code comprises:
 a) means for iteratively bisecting said range to select a test signal-to-noise ratio;   b) means for determining if said test signal-to-noise ratio achieves zero error; and   c) means for repeating means a and b until a desired accuracy in said signal-to-noise ratio is achieved.   
     
     
         31 . The means for generating high-rate codes from low-rate codes according to  claim 29 , wherein said means for progressively puncturing variable nodes from a set of non-punctured said variable nodes, comprises means for initializing by:
 means for calculating for each check node connected to at least one said variable node a number of said punctured variable nodes connected to said check nodes, wherein each of said check nodes is connected to only one said punctured variable node;   means for finding said set of said non-punctured variable nodes;   means for calculating for each said non-punctured variable node a number of said check nodes connected to each said non-punctured variable node, wherein each of said check nodes are connected to only one said punctured variable node; and   means for calculating for each said non-punctured variable node a sum of said punctured variable nodes connected to said check nodes, wherein said check nodes are connected to said non-punctured variable nodes.   
     
     
         32 . The means for generating high-rate codes from low-rate codes according to  claim 31 , wherein said means for progressively puncturing variable nodes from a set of non-punctured said variable nodes, further comprises a means for puncturing by finding said punctured variable node while a number of said punctured variable nodes at this step is less than a number of said punctured variable nodes for said desired rate. 
     
     
         33 . The means for generating high-rate codes from low-rate codes according to  claim 32 , wherein said means for finding said punctured variable node while a number of said punctured variable nodes at this step is less than a number of said punctured variable nodes for said desired rate comprises:
 a) means for finding a second set of said number of said non-punctured variable nodes in said set of said non-punctured variable nodes for which a number of neighboring of said check nodes is a minimum;   b) means for setting the punctured variable node to be the node in the second set if said number of said non-punctured variable nodes in said second set of means a is 1;   c) means for executing means ci-civ if the number of said non-punctured variable nodes of said second set of means a is >1;   ci) means for finding a subset of said second set of said non-punctured variable nodes from means a, in which the sum of said number of punctured variable nodes connected to said check nodes which are connected to said non-punctured variable nodes is a minimum;   cii) means for setting said punctured variable nodes to the single node in the subset in means ci if the number of said non-punctured variable nodes in said subset from means ci is 1;   ciii) means for choosing said variable nodes from said non-punctured variable nodes from means ci at random if the number of the non-punctured variable nodes found in the subset from means ci is greater than 1; and   civ) means for puncturing said chosen variable node and means for removing said punctured, chosen variable node from the set of non-punctured variable nodes.   
     
     
         34 . The means for generating high-rate codes from low-rate codes according to  claim 33 , wherein said means for progressively puncturing variable nodes from a set of non-punctured said variable nodes further comprises a means for updating, comprising:
 means for updating said number of punctured variable nodes connected to the check nodes for each of said check nodes neighboring said punctured variable nodes;   means for updating the number of said check nodes connected to said non-punctured variable nodes, wherein said check node is connected to only one said punctured variable node for each said variable node neighboring said check node; and   means for updating the sum of said punctured variable nodes connected to said check node, where said check node is connected to said non-punctured variable nodes for each said variable node neighboring said check node.   
     
     
         35 . The means for generating high-rate codes from low-rate codes according to  claim 34 , wherein said means for progressively puncturing variable nodes from a set of non-punctured said variable nodes, further comprises a means for maximizing a connectivity between the check nodes with only one punctured variable node and the other punctured variable nodes. 
     
     
         36 . The means for generating high-rate codes from low-rate codes according to  claim 35 , wherein said means for maximizing a connectivity between the check nodes with only one punctured variable node and the other punctured variable nodes, comprises:
 means for initializing a puncturing score to zero;   means for changing a random seed;   means for running said means of  claims 23 ,  29 ,  31 ,  32 , and  33  on said preceding code to get said desired punctured code;   means for calculating the puncturing score of the desired punctured code; and   means for choosing the puncturing pattern with the largest puncturing score if the puncturing score of the desired punctured code is greater than the puncturing score of the preceding code.   
     
     
         37 . An encoder which generates high-rate codes from low-rate codes, comprising:
 a memory, wherein said encoder is adapted to execute instructions stored in said memory comprising:   puncture a subset of codeword bits.   
     
     
         38 . The encoder which generates high-rate codes from low-rate codes according to  claim 37 , wherein said low-rate codes are parent codes. 
     
     
         39 . The encoder which generates high-rate codes from low-rate codes according to  claim 37 , wherein said instruction to puncture a subset of codeword bits comprises regular-irregular puncturing said subset of codeword bits, comprising:
 choose a parent code with a desired base rate;   find a set of non-punctured variable nodes in a preceding code for each rate in a set of desired rates;   calculate a number of variable nodes to be punctured to go from a preceding rate to a desired rate;   calculate alpha and beta such that a puncturing pattern on a non-punctured set is regular; and   puncture a pattern which is a function said alpha and said beta on said non-punctured set.   
     
     
         40 . The encoder which generates high-rate codes from low-rate codes according to  claim 37 , wherein said instruction to puncturing a subset of codeword bits comprises randomly puncture variable nodes. 
     
     
         41 . The encoder which generates high-rate codes from low-rate codes according to  claim 37 , wherein said instruction to puncture a subset of codeword bits comprises:
 progressive node puncture variable nodes to obtain a desired code from a preceding code.   
     
     
         42 . The encoder which generates high-rate codes from low-rate codes according to  claim 38 , wherein said parent codes are generated by executing the following instructions:
 copy a base graph;   permute end points of edges of a same type in copies of said base graph to produce a permuted graph; and   prune systematic input nodes in said permuted graph and said edges connected to them.   
     
     
         43 . The encoder which generates high-rate codes from low-rate codes according to  claim 39 , wherein said instruction to calculate a number of variable nodes to be punctured to go from a preceding rate to a desired rate uses the following formula:
     pm =Floor( N −( N−C )/ Rm−N   —   tm− 1),
   
       where pm is the number of variable nodes to be punctured, Rm is the desired rate, Rm−1 is a preceding rate, N and C are a number of variable nodes and check nodes in a lifted graph respectively, N_tm−1 is a total number of said punctured variable nodes in the lifted graph corresponding to a preceding code C{Rm−1}, and Floor ( ) represents a floor function. 
     
     
         44 . The encoder which generates high-rate codes from low-rate codes according to  claim 39 , wherein said instruction to calculate alpha and beta such that a puncturing pattern on the non-punctured set is regular uses the following formulas:
   alpha=Floor[( rm− 1 −pm )/( pm− 1)] and     beta= rm− 1−alpha( pm− 1)− pm,  
   
       where pm is the number of variable nodes to be punctured, rm−1 is a cardinality of the set of non-punctured redundancy variable nodes in preceding code C{Rm−1}, Rm−1 is a preceding rate, and Floor ( ) represents a floor function. 
     
     
         45 . The encoder which generates high-rate codes from low-rate codes according to  claim 39 , wherein said instruction to puncture a pattern which is a function said alpha and said beta on said non-punctured set comprises use a pattern [N1 {alpha nodes} N2 {alpha nodes} . . . Nm {beta nodes}], where N1, N2, . . . Np_m are the indices of the punctured variable nodes within the set of non-punctured redundancy nodes of cardinality rm−1. 
     
     
         46 . The encoder which generates high-rate codes from low-rate codes according to  claim 40 , further comprising an instruction to randomly search said subset of codeword bits, comprising:
 i) choose a parent code with a desired base rate;   ii) initialize a signal-to-noise ratio for each desired rate in the set of desired rates;   iii) find a set of non-punctured variable nodes in a preceding code with a preceding rate;   iv) calculate a number of variable nodes to be punctured to go from said preceding rate to a desired rate;   v) randomly choose said number of variable nodes to be punctured from said set of non-punctured variable nodes;   vi) construct a code from the preceding rate by puncturing said chosen number of variable nodes;   vii) run density evolution to test if said constructed code achieves a negligible error with the initialized signal-to-noise ratio;   viii) iteratively search for a new signal-to-noise threshold of said constructed code, set said constructed code as a winner code and set said signal-to-noise ratio equal to a new threshold if said constructed code achieves a negligible error with said signal-to-noise ratio; and   ix) repeat said random searching by repeating steps v through vii if said constructed code does not achieve a negligible error with said signal-to-noise ratio.   
     
     
         47 . The encoder which generates high-rate codes from low-rate codes according to  claim 41 , wherein said instruction to progressive node puncture variable nodes to obtain a desired code from a preceding code comprises:
 progressively puncture said variable nodes from a set of non-punctured said variable nodes of cardinality rm−1, wherein rm−1, is a number of members in the set of non-punctured redundancy variable nodes in a preceding code and wherein non-punctured redundant variable nodes of the preceding code may be punctured to yield the code of a desired rate.   
     
     
         48 . The encoder which generates high-rate codes from low-rate codes according to  claim 41 , wherein said instruction to iteratively search for a new threshold of said constructed code comprises:
 a) iteratively bisect said range to select a test signal-to-noise ratio;   b) determine if said test signal-to-noise ratio achieves zero error; and   c) repeat steps a and b until a desired accuracy in said signal-to-noise ratio is achieved.   
     
     
         49 . The encoder which generates high-rate codes from low-rate codes according to  claim 47 , wherein said instruction to progressively puncture variable nodes from a set of non-punctured said variable nodes, comprises an instruction to initialize by:
 calculate for each check node connected to at least one said variable node a number of said punctured variable nodes connected to said check nodes, wherein each of said check nodes is connected to only one said punctured variable node;   find said set of said non-punctured variable nodes;   calculate for each said non-punctured variable node a number of said check nodes connected to each said non-punctured variable node, wherein each of said check nodes are connected to only one said punctured variable node; and   calculate for each said non-punctured variable node a sum of said punctured variable nodes connected to said check nodes, wherein said check nodes are connected to said non-punctured variable nodes.   
     
     
         50 . The encoder which generates high-rate codes from low-rate codes according to  claim 1 , wherein said instruction to progressively puncture variable nodes from a set of non-punctured said variable nodes, further comprises an instruction to puncture by finding said punctured variable node while a number of said punctured variable nodes at this instruction is less than a number of said punctured variable nodes for said desired rate. 
     
     
         51 . The encoder which generates high-rate codes from low-rate codes according to  claim 50 , wherein said instruction to find said punctured variable node while a number of said punctured variable nodes at this instruction is less than a number of said punctured variable nodes for said desired rate comprises:
 a) find s second set of said non-punctured variable nodes in said set of said non-punctured variable nodes for which a number of neighboring of said check nodes is a minimum;   b) set the punctured variable node to be the node in the second set if said number of said non-punctured variable nodes in said second set of step a is 1;   c) execute instructions ci-civ if the number of said non-punctured variable nodes of said second set of step a is >1;   ci) find a subset of said second set of said non-punctured variable nodes from instruction a, in which the sum of said number of punctured variable nodes connected to said check nodes which are connected to said non-punctured variable nodes is a minimum;   cii) setting said punctured variable nodes to the single node in the subset of step ci if the number of said non-punctured variable nodes in said subset from instruction ci is 1;   ciii) choose said variable nodes from said non-punctured variable nodes in the subset from instruction ci at random if the number of the non-punctured variable nodes found in the subset from instruction ci is greater than 1; and   civ) puncture said chosen variable node and remove said punctured, chosen variable node from the set of non-punctured variable nodes.   
     
     
         52 . The encoder which generates high-rate codes from low-rate codes according to  claim 51 , wherein said instruction to progressively puncture variable nodes from a set of non-punctured said variable nodes, further comprises an instruction to update, comprising:
 update said number of punctured variable nodes connected to the check nodes for each of said check nodes neighboring said punctured variable nodes;   update the number of said check nodes connected to said non-punctured variable nodes, wherein said check node is connected to only one said punctured variable node for each said variable node neighboring said check node; and   update the sum of said punctured variable nodes connected to said check node, where said check node is connected to said non-punctured variable nodes for each said variable node neighboring said check node.   
     
     
         53 . The encoder which generates high-rate codes from low-rate codes according to  claim 52 , wherein said instruction to progressively puncture variable nodes from a set of non-punctured said variable nodes, further comprises an instruction to maximize a connectivity between the check nodes with only one punctured variable node and the other punctured variable nodes. 
     
     
         54 . The encoder which generates high-rate codes from low-rate codes according to  claim 53 , wherein said instruction to maximize a connectivity between the check nodes with only one punctured variable node and the other punctured variable nodes, comprises:
 initialize a puncturing score to zero;   change a random seed;   run said steps of instructions of  claims 41 ,  47 ,  49 ,  50 , and  51  on said preceding code to get said desired punctured code;   calculate the puncturing score of the desired punctured code; and   choose the puncturing pattern with the largest puncturing score if the puncturing score of the desired punctured code is greater than the puncturing score of the preceding code.   
     
     
         55 . An access terminal which generates high-rate codes from low-rate codes, comprising:
 a transmitter;   a receiver operably connected to said transmitter;   a processor operably connected to said transmitter and said receiver;   an antenna operably connected to said transmitter and said receiver; and   a memory operably connected to said processor, wherein said access terminal is adapted to execute software instructions stored in said memory comprising:   puncture a subset of codeword bits.   
     
     
         56 . The access terminal which generates high-rate codes from low-rate codes according to  claim 55 , wherein said low-rate codes are parent codes. 
     
     
         57 . The access terminal which generates high-rate codes from low-rate codes according to  claim 55 , wherein said instruction to puncture a subset of codeword bits comprises regular-irregular puncturing said subset of codeword bits, comprising:
 choose a parent code with a desired base rate;   finding a set of non-punctured variable nodes in a preceding code for each rate in a set of desired rates;   calculate a number of variable nodes to be punctured to go from a preceding rate to a desired rate;   calculate alpha and beta such that a puncturing pattern on a non-punctured set is regular; and   puncture a pattern which is a function said alpha and said beta on said non-punctured set.   
     
     
         58 . The access terminal which generates high-rate codes from low-rate codes according to  claim 55 , wherein said instruction to puncturing a subset of codeword bits comprises randomly puncture variable nodes. 
     
     
         59 . The access terminal which generates high-rate codes from low-rate codes according to  claim 55 , wherein said instruction to puncture a subset of codeword bits comprises:
 progressive node puncture variable nodes to obtain a desired code from a preceding code.   
     
     
         60 . The access terminal which generates high-rate codes from low-rate codes according to  claim 56 , wherein said parent codes are generated by executing the following instructions:
 copy a base graph;   permute end points of edges of a same type in copies of said base graph to produce a permuted graph; and   prune systematic input nodes in said permuted graph and said edges connected to them.   
     
     
         61 . The access terminal which generates high-rate codes from low-rate codes according to  claim 57 , wherein said instruction to calculate a number of variable nodes to be punctured to go from a preceding rate to a desired rate uses the following formula:
     pm =Floor( N −( N−C )/ Rm−N   —   tm− 1,
   
       where pm is the number of variable nodes to be punctured, Rm is the desired rate, Rm−1 is a preceding rate, N and C are a number of variable nodes and check nodes in a lifted graph respectively, N_tm−1 is a total number of said punctured variable nodes in the lifted graph corresponding to a preceding code C{Rm−1}, and Floor ( ) represents a floor function. 
     
     
         62 . The access terminal which generates high-rate codes from low-rate codes according to  claim 57 , wherein said instruction to calculate alpha and beta such that a puncturing pattern on the non-punctured set is regular uses the following formulas:
   alpha=Floor[( rm− 1 −pm )/( pm− 1)]; and     beta= rm− 1−alpha( pm− 1)− pm,  
   
       where pm is the number of variable nodes to be punctured, rm−1 is a cardinality of the set of non-punctured redundancy variable nodes in preceding code C{Rm−1}, Rm−1 is a preceding rate, and Floor ( ) represents a floor function. 
     
     
         63 . The access terminal which generates high-rate codes from low-rate codes according to  claim 57 , wherein said instruction to puncture a pattern which is a function said alpha and said beta on said non-punctured set comprises use a pattern [N1 {alpha nodes} N2 {alpha nodes} . . . Nm {beta nodes}], where N1, N2, . . . Np_m are the indices of the punctured variable nodes within the set of non-punctured redundancy nodes of cardinality rm−1. 
     
     
         64 . The access terminal which generates high-rate codes from low-rate codes according to  claim 58 , further comprising an instruction to randomly search said subset of codeword bits, comprising:
 i) choose a parent code with a desired base rate;   ii) initialize a signal-to-noise ratio for each desired rate in the set of desired rates;   iii) find a set of non-punctured variable nodes in a preceding code with a preceding rate;   iv) calculate a number of variable nodes to be punctured to go from said preceding rate to a desired rate;   v) randomly choose said number of variable nodes to be punctured from said set of non-punctured variable nodes;   vi) construct a code from the preceding rate by puncturing said chosen number of variable nodes;   vii) run density evolution to test if said constructed code achieves a negligible error with the initialized signal-to-noise ratio;   viii) iteratively search for a new signal-to-noise threshold of said constructed code, set said constructed code as a winner code and set said signal-to-noise ratio equal to a new threshold if said constructed code achieves a negligible error with said signal-to-noise ratio; and   ix) repeat said random searching by repeating steps v through vii if said constructed code does not achieve a negligible error with said signal-to-noise ratio.   
     
     
         65 . The access terminal which generates high-rate codes from low-rate codes according to  claim 59 , wherein said instruction to progressive node puncture variable nodes to obtain a desired code from a preceding code comprises:
 progressively puncture said variable nodes from a set of non-punctured said variable nodes of cardinality rm−1, wherein rm−1, is a number of members in the set of non-punctured redundancy variable nodes in a preceding code and wherein non-punctured redundant variable nodes of the preceding code may be punctured to yield the code of a desired rate.   
     
     
         66 . The access terminal which generates high-rate codes from low-rate codes according to  claim 64 , wherein said instruction to iteratively search for a new threshold of said constructed code comprises:
 a) iteratively bisect said range to select a test signal-to-noise ratio;   b) determine if said test signal-to-noise ratio achieves zero error; and   c) repeat steps a and b until a desired accuracy in said signal-to-noise ratio is achieved.   
     
     
         67 . The access terminal which generates high-rate codes from low-rate codes according to  claim 65 , wherein said instruction to progressively puncture variable nodes from a set of non-punctured said variable nodes, comprises an instruction to initialize by:
 calculate for each check node connected to at least one said variable node a number of said punctured variable nodes connected to said check nodes, wherein each of said check nodes is connected to only one said punctured variable node;   find said set of said non-punctured variable nodes;   calculate for each said non-punctured variable node a number of said check nodes connected to each said non-punctured variable node, wherein each of said check nodes are connected to only one said punctured variable node; and   calculate for each said non-punctured variable node a sum of said punctured variable nodes connected to said check nodes, wherein said check nodes are connected to said non-punctured variable nodes.   
     
     
         68 . The access terminal which generates high-rate codes from low-rate codes according to  claim 67 , wherein said instruction to progressively puncture variable nodes from a set of non-punctured said variable nodes, further comprises an instruction to puncture by finding said punctured variable node while a number of said punctured variable nodes at this instruction is less than a number of said punctured variable nodes for said desired rate. 
     
     
         69 . The access terminal which generates high-rate codes from low-rate codes according to  claim 68 , wherein said instruction to find said punctured variable node while a number of said punctured variable nodes at this instruction is less than a number of said punctured variable nodes for said desired rate comprises:
 a) find s second set of said non-punctured variable nodes in said set of said non-punctured variable nodes for which a number of neighboring of said check nodes is a minimum;   b) set the punctured variable node to be the node in the second set if said number of said non-punctured variable nodes in said second set of step a is 1;   c) execute instructions ci-civ if the number of said non-punctured variable nodes of said second set of step a is >1;   ci) find a subset of said second set of said non-punctured variable nodes from instruction a, in which the sum of said number of punctured variable nodes connected to said check nodes which are connected to said non-punctured variable nodes is a minimum;   cii) setting said punctured variable nodes to the single node in the subset of step ci if the number of said non-punctured variable nodes in said subset from instruction ci is 1;   ciii) choose said variable nodes from said non-punctured variable nodes in the subset from instruction ci at random if the number of the non-punctured variable nodes found in the subset from instruction ci is greater than 1; and   civ) puncture said chosen variable node and remove said punctured, chosen variable node from the set of non-punctured variable nodes.   
     
     
         70 . The access terminal which generates high-rate codes from low-rate codes according to  claim 69 , wherein said instruction to progressively puncture variable nodes from a set of non-punctured said variable nodes, further comprises an instruction to update, comprising:
 update said number of punctured variable nodes connected to the check nodes for each of said check nodes neighboring said punctured variable nodes;   update the number of said check nodes connected to said non-punctured variable nodes, wherein said check node is connected to only one said punctured variable node for each said variable node neighboring said check node; and   update the sum of said punctured variable nodes connected to said check node, where said check node is connected to said non-punctured variable nodes for each said variable node neighboring said check node.   
     
     
         71 . The access terminal which generates high-rate codes from low-rate codes according to  claim 70 , wherein said instruction to progressively puncture variable nodes from a set of non-punctured said variable nodes, further comprises an instruction to maximize a connectivity between the check nodes with only one punctured variable node and the other punctured variable nodes. 
     
     
         72 . The access terminal which generates high-rate codes from low-rate codes according to  claim 71 , wherein said instruction to maximize a connectivity between the check nodes with only one punctured variable node and the other punctured variable nodes, comprises:
 initialize a puncturing score to zero;   change a random seed;   run said steps of instructions of  claims 59 ,  65 ,  47 ,  48 , and  49  on said preceding code to get said desired punctured code;   calculate the puncturing score of the desired punctured code; and   choose the puncturing pattern with the largest puncturing score if the puncturing score of the desired punctured code is greater than the puncturing score of the preceding code.