Path encoding and decoding

Patent metadata

Field	Value
Publication number	US-9425825-B2
Application number	US-201514947101-A
Country	US
Kind code	B2
Filing date	Nov 20, 2015
Priority date	May 22, 2012
Publication date	Aug 23, 2016
Grant date	Aug 23, 2016

Abstract

This invention relates to a system, method and computer program product for encoding an input string of binary characters including: a cellular data structure definition including a starting empty cell; one or more path definitions defining paths through the data structure; a character reading and writing engine for writing a binary character to an empty cell with a predefined initial position; a next cell determination engine for determining a next empty cell by methodically checking cells along one of the paths in the data structure until an empty cell is located; a loop facilitator for looping back to the writing next character step and the determining next cell step until there are no more data characters or a next empty cell is not determined; and a serialization deserialization engine for methodically serializing the data structure into a one dimensional binary string of characters representing an encoded string of alphanumeric characters.

First claim

The invention claimed is:

1. A system for encoding an input string of binary characters, comprising:
a register for cellular data structure definition including a starting empty cell;
a register for one or more path definitions defining paths through the data structure;
a character reading and writing engine for writing a binary character to an empty cell with a predefined initial position;
a next cell determination engine for determining a next empty cell by methodically checking cells along one of the paths in the data structure until an empty cell is located;
a loop facilitator for looping back to the writing next character step and the determining next cell step until there are no more data characters or a next empty cell is not determined; and
a serialization deserialization engine for methodically serializing the data structure into a one dimensional binary string of characters representing an encoded string of alphanumeric characters.

2. A system according to claim 1 , wherein methodically checking cells along the path comprises traversing cells incrementally from the current cell in a current direction along the path to a new cell and wherein the new cell is the next cell if the new cell is an empty cell otherwise traversing again until an empty cell is located.

3. A system according to claim 1 , wherein methodically checking comprises jumping over one or more empty cells depending on conditions.

4. A system according to claim 1 , further comprising changing to a new path to locate an empty cell.

5. A system according to claim 1 , further comprising changing a current direction if a particular binary character has been written.

6. A system according to claim 5 , wherein using a different direction if traversing in the current direction would cross a boundary of the data structure.

7. A system according to claim 6 , wherein the current direction changes to an opposite direction if the current direction would cross a boundary of the two dimensional shape.

8. A system of decoding an input string of binary characters representing an encoded string of alphanumeric characters, comprising:
a register for storing a cellular data structure definition, the cellular data structure definition including a starting current cell;
a register for storing a data structure definition, the data structure definition for defining one or more paths through the data structure;
a serialization de-serialization engine for populating the cells with the binary characters using a defined transform so that each populated cell is full;
character reading and writing engine for reading a binary character from the current cell, writing it to an output string, and setting the current cell to empty;
a next cell determination engine for determining a next full cell by methodically traversing from the current cell to adjacent cells along the one or more paths in the data structure until a full cell is located; and
a loop facilitator for looping back to the reading next character step and the determining next cell step until there are no more cells in the data structure or a next full cell is not determined and whereby the output string can be presented as a decoded string of alphanumeric characters.

9. A system according to claim 8 , wherein methodically checking cells along the path comprises traversing cells incrementally from the current cell in a current direction along the path to a new cell and wherein the new cell is the next cell if the new cell is an empty cell otherwise traversing again until an empty cell is located.

10. A system according to claim 8 , wherein methodically checking comprises jumping over one or more empty cells depending on conditions.

11. A method of encoding an input string of binary characters, comprising:
defining a cellular data structure including a starting empty cell;
defining one or more paths through the data structure;
writing a binary character to an empty cell with a predefined initial position;
determining a next empty cell by methodically checking cells along one of the paths in the data structure until an empty cell is located;
looping back to the writing next character step and the determining next cell step until there are no more data characters or a next empty cell is not determined; and
methodically serializing the data structure into a one dimensional binary string of characters representing an encoded string of alphanumeric characters.

12. A method according to claim 11 , wherein methodically checking cells along the path comprises traversing cells incrementally from the current cell in a current direction along the path to a new cell and wherein the new cell is the next cell if the new cell is an empty cell otherwise traversing again until an empty cell is located.

13. A method according to claim 11 , wherein methodically checking comprises jumping over one or more empty cells depending on conditions.

14. A method according to claim 11 , further comprising changing to a new path to locate an empty cell.

15. A method according to claim 11 , further comprising changing a current direction if a particular binary character has been written.

16. A method according to claim 15 , wherein using a different direction if traversing in the current direction would cross a boundary of the data structure.

17. A method according to claim 16 , wherein the current direction changes to an opposite direction if the current direction would cross a boundary of a two dimensional shape.

18. A method of decoding an input string of binary characters representing an encoded string of alphanumeric characters comprising:
defining a cellular data structure including a starting current cell;
defining one or more paths through the data structure;
populating the cells with the binary characters using a defined transform so that each populated cell is full;

reading a binary character from the current cell; writing it to an output string, and setting the current cell to empty;
determining a next full cell by methodically traversing from the current cell to adjacent cells along the one or more paths in the data structure until a full cell is located;
looping back to the reading next character step and the determining next cell step until there are no more cells in the data structure or a next full cell is not determined; and
presenting the output string as a decoded string of alphanumeric characters.

19. A computer program product comprising a computer-readable storage medium having computer-readable program code embodied therewith, the computer-readable program code configured to perform a method for encoding an input string of binary characters representing alphanumeric characters when executed by a computer system, the method comprising:
defining a cellular data structure including a starting empty cell;
defining one or more paths through the data structure;
writing a binary character to an empty cell with a predefined initial position;
determining a next empty cell by methodically checking cells along one of the paths in the data structure until an empty cell is located;
looping back to the writing next character step and the determining next cell step until there are no more data characters or a next empty cell is not determined; and
methodically serializing the data structure into a one dimensional binary string of characters representing an encoded string of alphanumeric characters.

Assignees

• IBM

Inventors

• Bauchot Frederic J
• Legroux Marc Joel Herve

Classifications

• H03M7/14

  Conversion to or from non-weighted codes · CPC title

• H03M5/00

  Conversion of the form of the representation of individual digits · CPC title

• G06F40/126

  Character encoding · CPC title

• H03M7/30

  Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction · CPC title

• H03M7/40

  Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code · CPC title