The Inventors present Rake, an efficient algorithm for VDBS encoding. Rake reduces signal transitions and thereby reduces dynamic power dissipation on serial communication interfaces, by permitting a selectable amount of deviation from correctness in transmitted data with small overheads in practical applications.
It operates in two sweeps of a word, accumulating metadata in the first sweep and leveling out transitions in the second (hence the name, “Rake”). In the first phase, moving across the l-bit input words from least-significant bit (LSB) to most-significant bit (MSB), Rake stores the number of transitions seen-to-date in the transition count register. Rake stores the indices of these transitions in the transition indices array. In the second phase, Rake moves across the input in the opposite direction, from MSB to LSB, inspecting only the bit positions that have transitions. The algorithm performs checks to determine which transitions can be removed based on allowable deviations from correctness that might occur, and performs these changes. Rake is a highly efficient algorithm: for 24-bit values, it requires only 45 steps, as opposed to exact, optimal solutions that require exploring a space of 16 million values.