Integer string rule detection system

• US 5,428,709 A
• Filed: 08/20/1993
• Issued: 06/27/1995
• Est. Priority Date: 08/20/1993
• Status: Expired due to Term

• Current Assignee: Binary Services LLC (Intellectual Ventures LLC)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Banzhaf, Wolfgang
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): HAFIZ, TARIQ R
• Application Number:
  US08/109,666
• Time in Patent Office: 676 Days
• Field of Search: 395/13, 395/51, 395/10, 395/922, 395/22, 395/65-66
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: Y10S 706/922 Computer program preparation

Abstract

A system is provided for determining the rule or set of rules which govern the generation of a string of integers so as to ascertain the nature of the data represented by the string of integers, with the integer generation rule permitting genetic code determinations, optimization of communication channels through received signal analysis, curve fitting and determination of integer coding. For the analysis, means are provided to generate strings of integers from trial programs that are optionally derived from sequences of binary numbers. Error coefficients are derived when the integer strings generated by the trial programs are compared to the initial integer string. Means are provided to select a reduced set of trial programs based on the derived error coefficients, with the process of selection of trial programs being iterated until a single trial program is selected as the best trial program. This best trial program then specifies the most likely rule responsible for the generation of the initial strings of integers. The decoding system uses no a priori knowledge in the selection process, with the system providing automatic generation of algorithms instead of inaccurate fit functions. In one embodiment, the Subject System is implemented in a low-level binary representation, which is fast and easy to implement in hardware.

Claims

1. A method for determining a rule which governs the generation of a string of integers, comprising the steps of:

generating an input string of integers;

initially generating a set of trial programs for use in generating a set of trial integer sequences, each of said programs corresponding to a predetermined integer generating rule;

running said set of trial programs to generate a corresponding set of trial integer sequences;

comparing said input string of integers with each of said trial integer sequences and for generating an error measure corresponding to the difference therebetween; and

,

selecting which program in said set of trial programs executes, the execution of which results in the generation of an integer sequence most closely approximating said input integer string, thereby to identify the rule which governs the generation of said input string of integers.

2. The method of claim 1, wherein said step of generating said set of trial programs includes the step of iteratively selecting additional programs for generation of additional trial integer sequences such that additional integer sequences are compared with said input integer string until said error measure is below a predetermined threshold.

3. The method of claim 2, wherein said step of generating said set of trial programs includes the step of automatically initially generating a number of random programs for use as said set of trial programs.

4. The method of claim 3, wherein the number of additional programs exceeds the number of trial programs initially generated and wherein said selecting step includes the step coupled to said program generating means and responsive to said error measure for generating said additional number of trial programs.

5. The method of claim 4, wherein said selecting step includes the step of selecting either a larger or smaller number of additional trial programs responsive to said error measure such that for each subsequent iteration the error measure is either reduced or unchanged, thereby to permit more rapid reduction of said error measure and thus more rapid convergence to the most closely approximating trial integer sequence and corresponding trial program.