Adaptation of hierarchical codebooks

Abstract

An electronic device, a method, and computer readable media for adapting a hierarchical codebook. The electronic device includes a memory for storing a hierarchical codebook and a processor operably connected to the memory, which is configured to determine usage probabilities for codewords in the hierarchical codebook. The codewords are represented by nodes assigned to one of a plurality of tiers of the hierarchical codebook based on a tier identifier. The processor is also configured to change a structure of the hierarchical codebook based on the usage probabilities so that nodes associated with codewords having relatively higher usage probabilities are located closer to a root node than nodes associated with codewords having relatively lower usage probabilities, and select a codeword from the hierarchical codebook for use in wireless communication. The codeword is selected by a codeword selection procedure performed on the changed structure of the hierarchical codebook.

What is claimed is: 
     
       1. An electronic device comprising:
 a memory configured to store a hierarchical codebook; and 
 a processor operably connected to the memory, the processor configured to:
 determine usage probabilities for codewords in the hierarchical codebook, wherein the codewords are represented by nodes assigned to one of a plurality of tiers of the hierarchical codebook based on a tier identifier; 
 change a structure of the hierarchical codebook based on the usage probabilities so that nodes associated with codewords having relatively higher usage probabilities are located closer to a root node than nodes associated with codewords having relatively lower usage probabilities; and 
 select a codeword from the hierarchical codebook for use in wireless communication, wherein the codeword is selected by a codeword selection procedure performed on the changed structure of the hierarchical codebook. 
 
 
     
     
       2. The electronic device of  claim 1 , wherein to change the structure of the hierarchical codebook, the processor is configured to (i) update tier identifiers for the codewords in the hierarchical codebook based on the usage probabilities, wherein the tier identifiers indicate an order of traversing the hierarchical codebook during the codeword selection procedure or (ii) merge two or more of the codewords based on usage probabilities and a similarity of angular direction. 
     
     
       3. The electronic device of  claim 2 , wherein to merge the codewords the processor is further configured to:
 identify a first codeword with a first angular direction and a first usage probability; 
 identify a second codeword with a second angular direction and a second usage probability, wherein the second angular direction is similar to the first angular direction; 
 merge the first codeword and the second codeword to form a merged codeword with a combined usage probability that is a sum of the first usage probability and the second usage probability; and 
 provide the merged codeword with an updated tier identifier based on the combined usage probability. 
 
     
     
       4. The electronic device of  claim 1 , wherein to change the structure of the hierarchical codebook the processor is further configured to determine (i) whether recent search times for codeword selection procedures differ from historical search times for the codeword selection procedures or (ii) whether recent codeword usage probabilities differ from historical codeword usage probabilities, and
 wherein the structure of the hierarchical codebook is changed based on the determination. 
 
     
     
       5. The electronic device of  claim 1 , wherein to determine the usage probabilities the processor is configured to identify codeword usage patterns from a codeword usage history, wherein the codeword usage patterns include a probability that the codeword is selected for communication in a time interval and an average length of time for selecting the codeword. 
     
     
       6. The electronic device of  claim 1 , wherein the hierarchical codebook comprises a set of best narrow beam codewords for directions within an angular coverage region of wide beam codewords in the hierarchical codebook, wherein each of the set of best narrow beam codewords is a child node of one of the wide beam codewords. 
     
     
       7. The electronic device of  claim 1 , wherein:
 the hierarchical codebook is associated with at least two different branching factors, or 
 the hierarchical codebook has leaf nodes on at least two different tiers, or 
 at least one of the codewords is a child node for two or more codewords. 
 
     
     
       8. A method for adapting a hierarchical codebook, the method comprising:
 determining usage probabilities for codewords in the hierarchical codebook, wherein the codewords are represented by nodes assigned to one of a plurality of tiers of the hierarchical codebook based on a tier identifier; 
 changing a structure of the hierarchical codebook based on the usage probabilities so that nodes associated with codewords having relatively higher usage probabilities are located closer to a root node than nodes associated with codewords having relatively lower usage probabilities; and 
 selecting a codeword from the hierarchical codebook for use in wireless communication, wherein the codeword is selected by a codeword selection procedure performed on the changed structure of the hierarchical codebook. 
 
     
     
       9. The method of  claim 8 , wherein changing the structure of the hierarchical codebook comprises at least one of (i) updating tier identifiers for the codewords in the hierarchical codebook based on the usage probabilities, wherein the tier identifiers indicate an order of traversing the hierarchical codebook during the codeword selection procedure or (ii) merging two or more of the codewords based on usage probabilities and a similarity of angular direction. 
     
     
       10. The method of  claim 9 , wherein merging the codewords comprises:
 identifying a first codeword with a first angular direction and a first usage probability; 
 identifying a second codeword with a second angular direction and a second usage probability, wherein the second angular direction is similar to the first angular direction; 
 merging the first codeword and the second codeword to form a merged codeword with a combined usage probability that is a sum of the first usage probability and the second usage probability; and 
 providing the merged codeword with an updated tier identifier based on the combined usage probability. 
 
     
     
       11. The method of  claim 8 , wherein changing the structure of the hierarchical codebook comprises:
 determining (i) whether recent search times for codeword selection procedures differ from historical search times for the codeword selection procedures or (ii) whether recent codeword usage probabilities differ from historical codeword usage probabilities, and 
 wherein the structure of the hierarchical codebook is changed based on the determination. 
 
     
     
       12. The method of  claim 8 , wherein determining the usage probabilities comprises:
 identifying codeword usage patterns from a codeword usage history, wherein the codeword usage patterns include a probability that the codeword is selected for communication in a time interval and an average length of time for selecting the codeword. 
 
     
     
       13. The method of  claim 8 , wherein the hierarchical codebook comprises a set of best narrow beam codewords for directions within an angular coverage region of wide beam codewords in the hierarchical codebook, wherein each of the set of best narrow beam codewords is a child node of one of the wide beam codewords. 
     
     
       14. The method of  claim 8 , wherein:
 the hierarchical codebook is associated with at least two different branching factors, or 
 the hierarchical codebook has leaf nodes on at least two different tiers, or 
 at least one of the codewords is a child node for two or more codewords. 
 
     
     
       15. A non-transitory, computer-readable medium storing instructions that, when executed by a processor of an electronic device, cause the electronic device to:
 determine usage probabilities for codewords in a hierarchical codebook, wherein the codewords are represented by nodes assigned to one of a plurality of tiers of the hierarchical codebook based on a tier identifier; 
 change a structure of the hierarchical codebook based on the usage probabilities so that nodes associated with codewords having relatively higher usage probabilities are located closer to a root node than nodes associated with codewords having relatively lower usage probabilities; and 
 select a codeword from the hierarchical codebook for use in wireless communication, wherein the codeword is selected by a codeword selection procedure performed on the changed structure of the hierarchical codebook. 
 
     
     
       16. The non-transitory, computer-readable medium of  claim 15 , wherein instructions for changing the structure of the hierarchical codebook include further instructions that, when executed by the processor, cause the electronic device to (i) update tier identifiers for the codewords in the hierarchical codebook based on the usage probabilities, wherein the tier identifiers indicate an order of traversing the hierarchical codebook during the codeword selection procedure or (ii) merge two or more of the codewords based on usage probabilities and a similarity of angular direction. 
     
     
       17. The non-transitory, computer-readable medium of  claim 15 , wherein instructions to change the structure of the hierarchical codebook the processor include further instructions that, when executed by the processor, cause the electronic device to determine (i) whether recent search times for codeword selection procedures differ from historical search times for the codeword selection procedures or (ii) whether recent codeword usage probabilities differ from historical codeword usage probabilities, and
 wherein the structure of the hierarchical codebook is changed based on the determination. 
 
     
     
       18. The non-transitory, computer-readable medium of  claim 15 , wherein instructions to determine the usage probabilities include further instructions that, when executed by the processor, cause the electronic device to identify codeword usage patterns from a codeword usage history, wherein the codeword usage patterns include a probability that the codeword is selected for communication in a time interval and an average length of time for selecting the codeword. 
     
     
       19. The non-transitory, computer-readable medium of  claim 15 , wherein the hierarchical codebook comprises a set of best narrow beam codewords for directions within an angular coverage region of wide beam codewords in the hierarchical codebook, wherein each of the set of best narrow beam codewords is a child node of one of the wide beam codewords. 
     
     
       20. The non-transitory, computer-readable medium of  claim 15 , wherein:
 the hierarchical codebook is associated with at least two different branching factors, or 
 the hierarchical codebook has leaf nodes on at least two different tiers, or 
 at least one of the codewords is a child node for two or more codewords.