Groups of phase invariant codewords转让专利
申请号 : US15114398
文献号 : US10171107B2
文献日 : 2019-01-01
发明人 : Matthew D Gaubatz , Robert Ulichney , Steven J Simske
申请人 : Hewlett-Packard Development Company, L.P.
摘要 :
权利要求 :
The invention claimed is:
说明书 :
Technologies for enabling data-bearing media afford a number of interesting applications, including labels, packaging, signage, and documents in general. Non-limiting examples of data-bearing media may include data-bearing magnetic media (e.g., magnetic storage), data-bearing optical media optical storage), data-bearing atomic media (e.g., atomic storage), or data-bearing images.
One approach for enabling data bearing properties may be encoding information in a recoverable or readable manner in a halftone image. Halftone screening techniques represent one of the methods used in printing technologies heretofore to improve the quality of printed pieces. These techniques may improve the aesthetic qualities and fidelity of printed reproductions. Clustered-dot halftoning converts the original image into a series of dot clusters of varying size to simulate tonal difference, displaying detail in the image. In highlighted regions, darker areas of the image may be printed with larger dot clusters and lighter areas may be printed with smaller dot clusters. These different sized dots absorb the light reflecting from the paper in varying amounts, thereby giving the illusion of different shades of gray while printing with only black ink.
Some techniques allow messages to be encoded throughout an image such that the original message is recoverable when only a subset or window of that image is examined. In ones example, a codeword may be defined as a set of symbols, such as bits, representing a message. In another example, a phase invariant codeword may be defined as a set of symbols in which every circularly shifted version of the set represents the same message. By way of example, 101, 110 and 001 are all circularly shifted versions of 101 in one example implementation, a structured array of data-bearing elements of a data-bearing medium represents an array of bits. A certain number of the bits in such an array may represent a phase invariant codeword and may repeat such that positions of the bits in each line (e.g., rows or columns) are circularly shifted from positions of the hits in an immediately preceding line. This approach allows a portion of the data-bearing medium to include at least a shifted version of a set of bits representing a message such that there is no need to synchronise the codewords (i.e., locate the start or end of any subsequence of bits) in order to interpret the data in a given window of the data-bearing medium.
Unfortunately, current techniques, like the circular coding technique above, may be limited in that they may require prohibitive amounts of storage and/or computation in order to encode and decode longer messages, since the resources required grow exponentially with the length of the codeword. For instance, if the scheme is implemented with a simple table including ail the codewords packed in order, an 8 bit message encoder may require 384 bytes, a 16-bit message encoder may require 172 kilobytes, and a 32 bit message encoder may require 9.93 petabytes. Thus, it may be difficult to represent messages made up of longer bit strings using techniques available today, in view of this shortcoming, disclosed herein are a system, non-transitory computer readable medium, and method for encoding and decoding data on a data bearing medium. In one example, a message comprising a bit string is read and a plurality of substrings in the message may be associated with a phase invariant, codeword, in another example, a composite codeword comprising each phase invariant codeword associated with a substring from the message may be encoded in the data bearing medium. Rather than being limited by the resources required to define the mapping between messages and encoded codewords, the techniques disclosed herein allow longer messages to be encoded in turn, longer strings of data may be represented with a phase-invariant scheme. For example, a 32 bit massage encoder may be implemented with a memory structure requiring 360 Kilobytes and producing length-44 composite codewords, or requiring 3.84 kilobytes and producing a length-60 codeword, depending on how many substrings are used to represent the message. The resulting composite codeword length and associated coding efficiency may vary based on the input parameters. The aspects, features and advantages of the present disclosure will be appreciated when considered with reference to the following description of examples and accompanying figures. The following description does not limit the application; rather, the scope of the disclosure is defined by the appended claims and equivalents.
The computer apparatus 100 may also contain a processor 110 which may be any number of well known processors, such as processors from Intel® Corporation. In another example, processor 110 may be an application specific integrated circuit (“ASIC”). Non-transitory computer readable medium (“CRM”) 112 may store instructions that may be retrieved and executed by processor 110. As will be discussed in more detail below, the instructions may include an encoder 114 and a decoder 16. In one example, non-transitory CRM 112 may be used by or in connection with any instruction execution system that can fetch or obtain the logic from non-transitory CRM 112 and execute the instructions contained therein.
Non-transitory CRM 112 may comprise any one of many physical media such as, for example, electronic, magnetic, optical, electromagnetic, or semiconductor media. More specific examples of suitable non-transitory computer-readable media include, but are not limited to, a portable magnetic computer diskette such as floppy diskettes or hard drives, a read-only memory (“ROM”), an erasable programmable read-only memory, a portable compact disc or other storage devices that may be coupled to computer apparatus 100 directly or indirectly. The non-transitory CRM 112 may also include any combination of one or more of the foregoing and/or other devices as well.
While only one processor and one non-transitory CRM are shown in
The instructions residing in non-transitory CRM 112 may comprise any set of instructions to be executed directly (such as machine code) or indirectly (such as scripts) by processor 110. In this regard, the terms “instructions,” “scripts,” or “modules” may be used interchangeably herein. The computer executable instructions may be stored in any computer language or format, such as in object code or modules of source code. Furthermore, it is understood that the instructions may be implemented in the form of hardware, software, or a combination of hardware and software and that the examples herein are merely illustrative.
In one example, associations between phase invariant codewords and bit strings of a first length may be stored. Each phase invariant codeword may belong to a group of codewords having a particular property. In another example, encoder 114 may instruct processor 110 to read a message comprising a bit string of a second length longer than the first length. In yet a further example, encoder 114 may instruct processor 110 to divide the message into a plurality of substrings such that each substring may be smaller than the message of the first length. In other words, the substring may be of a shorter length than that of the original message. In another aspect, encoder 114 may instruct processor 110 to encode, on a data bearing medium, a composite codeword comprising each phase invariant codeword associated with a substring from the message.
Working examples of the system, method, and non-transitory computer readable medium are shown in
In block 202 of
In one aspect, the number of codeword groups may be a power of two and the number of phase invariant codewords in each group may be a power of two. As noted above, the particular property in the example of
By way of example, encoder 114 may read and encode the following message: 10010011. This message may be divided into the following four substrings: 10 01 00 11. The encoder 114 may search LUT 300 to obtain the phase invariant codeword associated with each smaller bit string divided from the message, in another aspect, encoder 114 may generate a composite codeword comprising each phase invariant codeword associated with a substring from the message. Thus, given the example above, the phase invariant codewords associated with each substring from the illustrative message are:
- 1010000 1101000 1110010 1111111
In the example above, a phase invariant codeword was selected from each group, however if is understood that any selection criteria may be used. For example, all phase invariant codewords may be selected from the same group or any combination of groups. In a further example, the phase invariant codewords above may be combined by regularly interspersing the symbols, to form a composite codeword:
- 1 1 1 1 0 1 1 1 1 0 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 0 0 1
- 1010000 1101000 1110010 1111111
Generally, phase invariant codewords of the following format:
- A1A2A3A4A5A6A7 B1B2B3B4B5B6B7 C1C2C3C4C5C6C7 D1D2D3D4D5D6D7 may be interspersed to form the following composite codeword:
- A1B1C1D1A2B2C2D2A3B3C3D3A4B4C4D4A5B5C5D5A6B6C6D6A7B7C7D7
Referring back to
In one example, decoder 118 may instruct processor 110 to read at least a portion of a composite codeword encoded on the data bearing medium and determine the substring associated with a phase invariant codeword in the composite codeword, in another aspect, decoder 116 may determine the group to which the phase invariant code word belongs in order to determine the substring associated with the phase invariant code word.
The table below compares storage amounts that may be required to encode and decode different message lengths. The first (leftmost) column displays different message lengths; the second column from the left shows an approximate amount of storage needed to store a message of a respective length using conventional techniques; the third column from the left shows an approximate amount of storage needed to store a message of a respective length using the techniques disclosed herein, when two groups of phase invariant codewords are utilized; finally, the fourth column from the left shows an approximate amount of storage needed to store a message of a respective length using the techniques disclosed herein, when four groups of phase invariant codewords are utilized. The table below illustrates how the techniques disclosed herein enable messages of a given length to be encoded using less storage to represent associations between codewords and message bits.
Advantageously, the above-described system, non-transitory computer readable medium, and method allow the encoding of longer messages on a data bearing medium. Rather than being limited by other conventional approaches, the techniques disclosed herein allow more flexibility by associating substrings in the message with different phase invariant codewords. In turn, longer messages may be encoded and users may be able to obtain even more information from data bearing media under the same constraints on computational resources.
Although the disclosure herein has been described with reference to particular examples, it is to be understood that these examples are merely illustrative of the principles of the disclosure. It is therefore to be understood that numerous modifications may be made to the examples and that other arrangements may be devised without departing from the spirit and scope of the disclosure as defined by the appended claims. Furthermore, while particular processes are shown in a specific order in the appended drawings, such processes are not limited to any particular order unless such order is expressly set forth herein. Rather, various steps can be handled in a different order or simultaneously, and steps may be omitted or added.