Method and system for prioritizing data values for robust data representation

Methods, systems and data structures select prioritized robust data values from a plurality of available data values formed by a plurality of data bits, each capable of exhibiting a bit value. Available data values are arranged into a gray code format, and alternate values of gray code format are selected to form a value map. An optional complementary value map may also be formed from the remaining data values. The value map is then prioritized according to bit adjacencies, wherein bit adjacencies are defined by contiguous bits within one of the data values that exhibit a common bit value. Priority may be given to data values having shortest and/or fewest bit adjacencies.

TECHNICAL FIELD

The present invention generally relates to data representation, and more particularly relates to methods and systems for prioritizing values in data maps for robust data representation.

BACKGROUND

Computing devices, particularly those found in various automotive, industrial, aerospace and other commercial settings, commonly represent operating modes or other information with sequences of binary digits or “bits” called “data values”. A conventional Karnaugh map, for example, is one technique for generating data values for a given number (“n”) bits. Conventional Karnaugh mapping techniques can be used to identify up to 2ndata values from the n bits. The resulting values can be stored in memory and/or exchanged with other computing modules to represent operating states or other appropriate information.

As digital data is stored, processed, consumed and/or shared between modules, bit errors can occur due to environmental factors, hardware faults and other causes. To ensure that data values are reliable, computing systems frequently incorporate error checking techniques such as parity checks, cyclic redundancy checks (CRCs) and/or the like. Conventionally, a program module preparing a data message computes a digital verification code based upon the contents of the message using a particular algorithm. The resulting verification code can then be appended to the message during transmission. The receiving module verifies the code using the same algorithm as the transmitting module to ensure that the contents of the message did not change during transmission; that is, by comparing a code computed prior to transmission with a code computed according to the same algorithm after transmission, the contents of the message can be verified to ensure that no bit errors occurred during transmission. Examples of well-known algorithms for computing reliable verification codes include the so-called CRC32 and MD4 algorithms, among others. While error checking routines are highly reliable, they do exhibit several disadvantages in terms of bandwidth and computing resources. Particularly in the vehicle setting, where computing resources and communications bandwidth are limited, the additional space and time required to transmit verification codes can be undesirable.

It is therefore desirable to formulate a data representation scheme that is capable of efficiently representing data without sacrificing robustness or accuracy. Moreover, it is desirable to create a technique for generating data values for such schemes. Furthermore, other desirable features and characteristics will become apparent from the subsequent detailed description and the appended claims, taken in conjunction with the accompanying drawings and the foregoing technical field and background.

BRIEF SUMMARY

According to various exemplary embodiments, methods, systems and data structures select prioritized robust data values from available data values formed by a plurality of data bits that are each capable of exhibiting a bit value. Available data values are arranged into a gray code format, and alternate values of gray code format are selected to form a value map. An optional complementary value map may also be formed from the remaining data values. The value map is then prioritized according to bit adjacencies, wherein bit adjacencies are defined by contiguous bits within one of the data values that exhibit a common bit value. Priority may be given to data values having shortest and/or fewest bit adjacencies.

In various further embodiments, the prioritized data values may be used to represent state data, variable data or the like. By selecting the value map to include only those data values that differ from each other by at least two bit values, susceptibility to bit errors is substantially reduced. That is, any single bit errors are readily identified (e.g. in a complementary value map) from the structure of the value map, thereby reducing the need for separate error-checking structures in many embodiments. Moreover, susceptibility to nibble, byte and/or other data errors can be appropriately reduced by prioritizing data values with shorter and/or fewer bit adjacencies.

DETAILED DESCRIPTION

According to various exemplary embodiments, robust data values are selected to determine the most robust values or sets of values for representing data. By properly choosing the bit sequences used in each data value, bit errors occurring during processing or transmission can be readily identified without the need for additional verification codes or the like. In a system wherein data values represent operating states, for example, data values can be assigned to the various operating states in a manner that requires any state transition to exhibit multiple bit transitions. If a single bit transition does occur due to a hardware fault or other undesirable event, the resulting data value will be immediately recognizable as invalid without the need for further error checking. Similar constraints can be applied to prevent nibble (4-bit), byte (8-bit) or other errors.

The particular data values used may be prioritized and/or selected using the techniques described herein. Generally speaking, data values are prioritized such that those values having the shortest and fewest bit adjacencies are given highest priority. “Bit adjacency” refers to two or more contiguous bits that have the same bit value (e.g. “0” or “1”). Because the most common hardware faults tend to produce errors in single bits or in groups of contiguous bits (particularly four and eight bit groups), avoiding bit adjacencies tends to increase the robustness of the data map. Robustness is also improved by selecting data values that differ from each other by multiple bit values, and/or by imposing other constraints.

The techniques described herein may be applied in any computing context, including any automotive, aerospace, commercial, governmental, industrial or consumer setting. By way of example only, data values could be used to represent operating states used within a control system. To illustrate just one context wherein data values may be used,FIG. 1shows an exemplary automotive control system100. System100shown inFIG. 1includes a supervisory controller102that communicates with any number of sub-modules104A–E as appropriate. Control module102suitably provides appropriate signals112A–E to one or more sub-modules104A–E based upon operator commands106, sensor data106, feedback received from modules104A–E, processed data and/or any other sources. Control module102typically executes on any type of processor or other control circuitry114having any associated digital memory116and other conventional hardware resources as appropriate. Sub-modules104A–E similarly execute on any type of processing or control hardware, and may variously reside on the same or different hardware as control module102. To that end, each of the modules102and104shown inFIG. 1are intended as logical modules capable of inter-communicating with each other in any manner.

Data communications between control module102and sub-modules104A–E take place in any appropriate manner. Data communications may take place via any serial or parallel data connection, for example, or across any conventional wired or wireless data link. Alternatively, signals112A–E may represent signals passed internally within a processor, controller or other component. In embodiments wherein one or more sub-modules104A–E reside on the same hardware as control module102, for example, signals112A–E may represent data structures formed in memory116and/or processed by controller114. Signals112A–E (or any subset thereof) may also be provided to or from other components (e.g. sensors, displays, other controllers, etc.) as appropriate.

Data signals112A–E may be electrically and/or logically formatted in any appropriate manner. In an exemplary embodiment, signals112A–E are capable of transporting a data structure that represents various operating states of system100and/or various sub-modules104A–E. Through proper selection and assignment of binary digit (“bit”) values used to represent the various operating modes, any errors occurring during processing or transmission of signals112A–E can be readily identified within the data structure, as described more fully below. Again,FIG. 1is simply one example of an environment wherein data values may be used. Other equivalent embodiments may use any number of modules102,104arranged in any fashion and communicating in any manner.

Referring now toFIG. 2, an exemplary process200for creating robust data value maps suitably includes the broad steps of arranging the values available in a gray code format (step202), selecting alternate values for a value map and/or complementary value map (step204), determining bit adjacencies for each value in the map (step206), and prioritizing the values within the map according to the size and number of bit adjacencies present in each value (step210). Process200may be executed manually and/or in any automated manner, such as using a digital computer. In the latter case, some or all of the steps in process200may be executed by instructions stored in a digital memory (e.g. memory116inFIG. 2) or other storage medium. The various steps shown inFIG. 2may be logically or temporally arranged in any manner, any need not execute according to the particular logic shown in the figure. Moreover, the various steps shown may be combined, supplemented or modified in any manner.

According to the exemplary embodiment of process200shown inFIG. 2, each of the available data values are initially listed in gray code format (step202). The “available” values are suitably dependent upon the number of bits available, as described more fully below. Three conventional data bits, for example, are capable of representing eight data values (“000”, “001”, “010”, “011”, “100”, “101”, “110” and “111”), with additional bits providing additional available values.

Process200begins by arranging or otherwise organizing available values into gray code format (step202). The ordering may be executed manually, with a computer spreadsheet or other program, or in any other appropriate manner. “Gray code” refers to an ordered list of values organized such that only one bit changes from one value to the subsequent value in the list. Exemplary gray code sequences for three eight three-bit values described above include <000, 001, 011, 010, 110, 111, 101, 100> and <000, 010, 011, 001, 101, 111, 110, 100>. Accordingly, many value lists may be placed into any of several gray code formats. Further, the gray code sequences need not start with an “all-zero” or “all-one” state, but may be initiated with any value.

Alternating gray code values are then selected to create a map of robust values that can be used to represent state information or other data (step204). Because gray code values differ from each other by a single bit transition, alternating gray code values can be expected to differ from each other by at least two bit transitions, thereby creating robustness in the various states. In a further optional embodiment, step204involves creating two separate maps of robust values from the gray coded sequence (e.g. by placing the even numbered values into one map and odd numbered values in a separate map). Each of the two maps created in this manner suitably represent complementary invalid states of the other map; that is, states that are valid in one map are invalid in the other map, and vice versa. This concept is explored more fully below.

Continuing with the exemplary process200shown inFIG. 2, the value map created in step202is appropriately evaluated to determine the most desirable values used to represent state data. Typically, the states that are least susceptible to bit, nibble, byte or other errors are identified as the priority values for use in actual data structures. Undetectable bit, nibble and byte errors are most likely to occur in values with sequences of contiguous bits having the same value. That is, hardware faults tend to create contiguous sequences of identical bits, making such faults harder to detect if the values used to represent actual data have similarly long contiguous sequences of identical values.

Accordingly, one technique for prioritizing robust states involves identifying bit adjacencies in each potential value, and giving priority to those values with shortest and/or fewest bit adjacencies. As shown inFIG. 2, this may be accomplished by manually or automatically determining the number and type of bit adjacencies (step206) for each value present in the map (step208). AlthoughFIG. 2shows steps206and208as executing while the map is being created from alternate gray code values, in practice step206may be executed at any point in process200. The determination and arranging functions of step206and210, for example, could be combined in an equivalent embodiment.

The value map is manually or automatically sorted or otherwise prioritized in any appropriate manner (step210). In an exemplary embodiment, values with the shortest bit adjacencies are given highest priority, with the number of bit adjacencies also taken into consideration. In this manner, values with unlike adjacent bits are given higher priority in the map than values with similar adjacent bits. Those values with no bit adjacencies, for example, will be given highest priority, followed by values with only two-bit adjacencies. Of those values having two-bit adjacencies, those with the fewest number of adjacencies may be given higher priority than those values with more adjacencies. If the value map includes values with three-bit or larger adjacencies, priority is next given to values having only one three-bit adjacency, followed by combinations of two and three-bit adjacencies. For value map of n bits, adjacencies having lengths from two bits to n−1 bits in length are appropriately considered, with values having longer bit adjacencies generally receiving lower priority.

Although values having equal numbers of longer adjacencies may be prioritized according to the number or frequency of smaller adjacencies also present in the data value (e.g. with values having fewer smaller adjacencies having priority over values with more frequent smaller adjacencies), priority is appropriately given to adjacency size before adjacency frequency. That is, a value with a single three-bit adjacency and multiple two-bit adjacencies would have priority over a value having multiple three-bit adjacencies.

Because the techniques described herein may be applicable across a wide range of computing systems and environments, the particular prioritization routine used may vary significantly from embodiment to embodiment. Although longer bit adjacencies are typically given lower priority in the examples herein, for example, other processes200may actually grant higher priority to values with bit adjacencies, and/or may differently prioritize bit values according to increasing or decreasing bit size and/or frequency. Alternate embodiments may therefore use other sorting or prioritization techniques without departing from the concepts set forth herein.

The evolution of an exemplary set of prioritized and robust data maps312and314is shown inFIG. 3. These concepts of sorting and prioritization may be readily applied to any number of values formed from bit streams of any size. That is, the concepts set forth in process200and inFIG. 3could be used to create priority maps representing values having any length, including values of tens, hundreds or even more bits. Various additional concepts for handling very large value maps are described more fully below.

Value map302shows an exemplary sequence of three bit values in gray code form. Map302shown inFIG. 3also includes a decimal equivalent for each binary value, although this equivalent is provided simply for ease of understanding and reference, and may not be present in all embodiments. Placing alternate values into separate sets results in two complementary maps304and306, with values in each map representing invalid states of the other map. That is, each of the values that are valid within map304(e.g. decimal values 0, 3, 6 and 5) would be invalid in systems based upon map306, and vice versa.

The number of bit adjacencies present in each value listed in maps304and306are shown in tables308and310, respectively. Decimal value “0” in map304, for example, has a single three-bit adjacency, whereas values “3” and “6” each have one two-bit adjacency, and value “5” has no bit adjacencies. Similarly, value “7” in map306has a single three-bit adjacency, and values “1” and “4” have single two-bit adjacencies.

Using the preference scheme described above in conjunction withFIG. 2, the resulting maps312and314present the various robust values in a manner that gives preference to those values having smaller and fewer bit adjacencies. Values “5” and “2” are therefore shown with highest priority, since these two states have no bit adjacencies. Values “3” and “6” in map312and values “4” and “1” in map314are next in priority, with values “0” and “7” having the lowest priority due to the three-bit adjacency present in each of these values. In the exemplary embodiment ofFIG. 3, no preference is given to whether the adjacent bits are set to “0” or “1”. That is, adjacent “0” bits are considered in the same manner as adjacent “1” bits. Alternate embodiments, however, may give preference to either bit value. In embodiments wherein data structures are initialized to an “all-zero” form, for example, preference may be given to “0” states over “1” states, since “0” states less likely to result from bit errors. Conversely, embodiments initialized to an “all-one” form may give preference to “1” values. Further, values “3” and “6” in map312may be exchanged with each other without affecting priority, since each of these values exhibits a single two-bit adjacency. Values “4” and “1” in table314could be similarly exchanged. Other factors may also be considered in establishing value priority.

Value maps312and314therefore present two complementary lists of values suitable for representing operating states or other information within computing system100(FIG. 1). The values shown closer to the top of maps312and314generally exhibit the least susceptibility to bit errors, and may therefore be the most preferable for use in representing state data or other information within system100. Stated another way, maps312and314show the highest-priority data values for certain applications arranged closest to the top of the maps. Similarly, values toward the bottom of the maps generally represent values with more bit adjacencies than those values shown higher in the map; these states therefore exhibit reduced immunity to bit, nibble and/or byte faults in certain applications, and can be said to have a “lower priority” for use in representing state data or other information in those applications.

Nevertheless, each of the values contained within each map312and314are robust with respect to each other; that is, any transition from one value to another valid value requires at change in the state of at least two bits. As a result, no single bit error (or any nibble or byte error) in a valid value could produce another valid value within the map, thereby providing improved robustness against such errors. Further, because the two maps312and314are complementary to each other, the values in each map represent states that are invalid according to the other map. That is, the various states in map314represent invalid operating states for map312, and vice versa. By checking received or processed data values against values maintained in the complementary map, then, a processing module or device may readily identify any inaccuracies in the data. That is, the complementary map may be used in some embodiments to identify errors or other issues in received or processed data.

The various data values may be transmitted or processed in any manner. In an exemplary embodiment, a data structure is formulated by a program or device to use one or more values within a value map to represent state data or the like. This data structure may then be processed, stored and/or transmitted to a receiving program, device or other module as appropriate.

Again, the concepts shown inFIG. 3with respect to three-bit maps could be applied to larger maps having any number of bits.FIGS. 4 and 5, for example, show exemplary value maps formulated according to the above-described techniques as applied to four and five bit values, respectively.FIG. 4therefore presents two complementary maps402and404suitable for representing up to eight robust data states, andFIG. 5presents complementary maps502and504suitable for representing as many as sixteen robust data states. Equivalent maps could be generated for values having six or more bits using the concepts set forth above.

Larger bit streams may be subdivided into two or more sub-sections of any length in various further embodiments. A conventional twelve-bit data sequence, for example, is typically capable of representing up to 4096 (equal to 212) non-robust states or 2048 (212-1) robust values. The 4096 non-robust states could be equivalently represented with thirteen-bit robust data values (with the additional bit providing additional states used for robustness), or by dividing the twelve-bit variable into multiple robust portions. Twelve bits could be divided into three four-bit portions, for example, with each portion represented by a five-bit robust map such as that shown inFIG. 5above. Alternatively, the twelve bits could be divided into four three-bit portions, with each non-robust three-bit portion represented by a robust four-bit robust map such as that shown inFIG. 4above. Other options include representing only a portion of the variable with robust data values. A twelve-bit non-robust variable, for example, could be represented by separating the twelve-bits into a three-bit portion and a nine-bit portion. A robust ten-bit map (capable of representing up to 512 robust states) could then be used to represent the most significant nine bit portion, and conventional non-robust data could represent the three remaining bits.

Further, the various representation techniques may be combined in any manner. A twelve-bit non-robust variable could be represented with three non-robust bits, for example, with the remaining nine bits subdivided into a five-bit and a four-bit portion that could be represented with robust maps of six and five bits, respectively. When variables are divided into multiple sections, various embodiments further select data values that avoid bit adjacencies between sections. This may be accomplished, for example, by excluding values that have bit adjacencies in the outermost bits that may abut against similar adjacencies in other data sections, thereby creating larger adjacencies that could be relatively more difficult to differentiate from nibble or byte faults. Again, the particular data representation schemes and value assignments may vary significantly from embodiment to embodiment.

Using the various techniques and systems described above, various benefits may be achieved. Robust data values as described herein provide improved resistance to bit, nibble and/or byte errors, for example, in a relatively space-efficient manner, thereby providing an effective balance between throughput and security for many applications. Although the various embodiments are most frequently described with respect to automotive applications, the invention is not so limited. Indeed, the concepts, systems and structures described herein could be readily applied in any transportation, aeronautical, governmental, industrial, commercial or other setting.

While at least one exemplary embodiment has been presented in the foregoing detailed description, a vast number of variations exist. The exemplary embodiments described herein are intended only as examples, and are not intended to limit the scope, applicability, or configuration of the invention in any way. Rather, the foregoing detailed description will provide those skilled in the art with a convenient road map for implementing one or more exemplary embodiments. Various changes can therefore be made in the functions and arrangements of elements set forth herein without departing from the scope of the invention as set forth in the appended claims and the legal equivalents thereof.