Method and apparatus for writing binary data with low power consumption

Abstract

Systems and methodologies are provided herein for representing information in a data processing system with low power consumption. As described herein, parity relationships between multiple nodes of to-be-written binary information and original information can be leveraged as described herein to reduce the amount of toggling required to write information in a memory, thereby reducing power consumption. Various algorithms for leveraging parity relationships are described herein, including a Champagne Pyramid Parity Check (CPPC) algorithm and a Tree-Based Parity Check (TBPC) algorithm.

1 . A method of writing binary information in a memory, comprising:
 identifying binary information to be stored by a memory;   generating a hierarchical data structure comprising a plurality of nodes, the plurality of nodes comprise respective information bits currently stored by the memory;   determining respective parity values of nodes in a bottom row of the hierarchical data structure; and   toggling binary values of one or more nodes in the hierarchical data structure such that the respective parity values of the nodes in the bottom row of the hierarchical data structure match respective corresponding bits in the binary information to be stored by the memory.   
     
     
         2 . The method of  claim 1 , wherein the generating a hierarchical data structure comprises generating one or more binary pyramid structures, and a number of nodes at the bottom row of the one or more binary pyramid structures equals a number of bits in the identified binary information. 
     
     
         3 . The method of  claim 2 , wherein the toggling comprises providing toggling indications for respective nodes at the bottom row of the binary pyramid structure for which a determined parity value for the node differs from a corresponding bit of the identified binary information; 
     
     
         4 . The method of  claim 3 , wherein the toggling comprises:
 identifying groups of consecutive nodes for which a toggling indication is provided;   replacing toggling indications provided by respective nodes in an identified group of consecutive nodes with a single toggling indication at the lowest common predecessor node to each node in the identified group of consecutive nodes; and   toggling binary values of nodes in the one or more binary pyramid structures for which toggling indications are provided.   
     
     
         5 . The method of  claim 2 , wherein the determining comprises determining a parity value for a node in a binary pyramid structure by performing an exclusive-OR operation on the binary value of a node, a parity value for a left source node to the node for which a parity value is being calculated, a parity value for a right source node to the node for which a parity value is being calculated, and a parity value for an upper source node that is a common source node of the left source node and the right source node. 
     
     
         6 . The method of  claim 1 , wherein the generating a hierarchical data structure comprises generating a complete N-ary tree structure, and a bottom row of the tree structure corresponds to leaf nodes of said tree structure. 
     
     
         7 . The method of  claim 6 , wherein:
 the generating a hierarchical data structure further comprises providing one or more said tree structures such that a number of leaf nodes of the one or more tree structures equals a number of bits in the identified binary information; and   the determining comprises determining parity values for respective leaf nodes of the one or more tree structures by determining parity of nodes in paths from the respective leaf nodes to a root node.   
     
     
         8 . The method of  claim 7 , wherein the toggling comprises:
 obtaining a toggle array by comparing respective parity values for the leaf nodes of the one or more tree structures and corresponding bits in the identified binary information;   constructing one or more toggle trees corresponding to the one or more tree structures at least in part by using respective elements of the toggle array as leaf nodes; and   toggling binary values of respective nodes of the one or more tree structures corresponding to respective highest nodes in the one or more toggle trees for which all leaf nodes indicate that parity values for the leaf nodes do not match corresponding bits in the identified binary information.   
     
     
         9 . The method of  claim 6 , wherein the determining comprises determining a parity value for a node in a tree structure by performing an exclusive-OR operation between the binary value of a node and a parity value for a parent node of the node for which a parity value is being calculated. 
     
     
         10 . The method of  claim 1 , wherein the information bits currently stored by the memory correspond to a previous communication of data, the identified binary information corresponds to a subsequent communication of data, and the method further comprises conducting the subsequent communication of data by transmitting one or more toggling positions that transform data corresponding to the previous communication of data to the identified binary data. 
     
     
         11 . A computer-readable medium having stored thereon instructions operable to perform the method of  claim 1 . 
     
     
         12 . A system for recording binary information, comprising:
 a champagne pyramid component that groups storage locations for respective information bits in a memory into at least one binary pyramid structure having a plurality of nodes respectively corresponding to the storage locations;   a parity check component that determines parity values of respective nodes in a bottom row of the at least one binary pyramid structure based on original information written in the memory; and   a toggling component that toggles binary values of one or more nodes in the at least one binary pyramid structures such that parity values of nodes in the bottom row of the at least one binary pyramid structure match corresponding bits in binary information to be recorded in the memory.   
     
     
         13 . The system of  claim 12 , further comprising a comparison component that provides toggling indications for respective nodes at the bottom row of the at least one binary pyramid structure for which determined parity values for the respective nodes differ from corresponding bits of the binary information to be recorded in the memory. 
     
     
         14 . The system of  claim 13 , further comprising a flavor adding optimization component that identifies groups of consecutive nodes in the bottom row of the at least one binary pyramid structure for which a toggling indication is provided and replaces toggling indications provided by respective nodes identified groups of consecutive nodes with a single toggling indication at the lowest common predecessor node to each node in the identified group of consecutive nodes. 
     
     
         15 . The system of  claim 14 , wherein the toggling component toggles binary values of respective nodes in the at least one binary pyramid structure for which toggling indications are provided. 
     
     
         16 . A system for recording binary information, comprising:
 a tree component that stores information in a memory as at least one complete N-ary tree structure having a plurality of nodes respectively corresponding to storage locations in the memory;   a parity check component that determines respective parity values for leaf nodes of the at least one complete N-ary tree structure based on original information written in the memory; and   a modification component that modifies binary values of one or more nodes in the at least one complete N-ary tree structure such that the parity values of the leaf nodes match corresponding bits in binary information to be recorded in the memory.   
     
     
         17 . The system of  claim 16 , further comprising a comparison component that establishes one or more toggle arrays by comparing respective parity values for the leaf nodes of the one or more complete N-ary tree structures to corresponding bits in the binary information to be recorded in the memory. 
     
     
         18 . The system of  claim 17 , further comprising a fountain investigation component that constructs one or more toggle trees corresponding to the one or more complete N-ary tree structures, wherein the one or more toggle trees utilize respective elements of the one or more toggle arrays as leaf nodes. 
     
     
         19 . The system of  claim 18 , further comprising a modification location determination component that identifies nodes of the at least one complete N-ary tree structure that correspond to respective highest nodes in the one or more toggle trees for which all leaf nodes indicate that parity values for the leaf nodes do not match corresponding bits in the binary information to be recorded in the memory. 
     
     
         20 . A system for recording binary information, comprising:
 means for providing binary information to be written in a memory;   means for providing a hierarchical data structure comprising a plurality of nodes that represent original information written in the memory;   means for determining respective parity values of nodes at a bottom row of the hierarchical data structure; and   means for toggling binary values of one or more nodes of the hierarchical data structure such that the respective parity values of the nodes at the bottom row of the hierarchical data structure match corresponding bits in the provided binary information.