User:Msiddalingaiah/Ideas

Just some things I've been thinking about...

Wireless

1. RFID
   • ATiny
   • Very low power, short range proximity authentication (e.g. lock/unlock doors)
   • Symmetric transceiver
     • Crystal VCO/mixer
     • 5kHz IF or less
     • PLL demodulator adjusts crystal VCO
     • Precision rectifier (opamp w/two diodes) AM detector
2. Challenge/response
   • Homodyne transceiver using TEA cipher
3. Homodyne digital receiver
   • Low IF PLL
   • Flip-flop data slicer
4. LC local oscillator
   • Amplitude stabilized
   • Frequency compensation using diode junction temperature transducer
5. Overtone crystal oscillator
   • Negative resistance of Hartley oscillator increases with frequency
6. Antennas
   • Short helix with loading coil
7. Remote monitor
   • Temperature, wind speed, humidity
   • Particulates measurement using smoke detector
   • Voltage, current, peak, average
   • Light, sound

Embedded systems

Low cost embedded systems

1. x86
2. 68000
   • Old Palm handhelds
3. ARM
   • Gameboy advance
4. AVR
   • ATiny
   • ATmega
5. Z80
   • Java arcade simulator
   • Gameboy
6. 6502/6809
   • Java simulators

Fast arc tangent

How do you compute arc tangent quickly? I stumbled on an excellent article by Jim Shima:

http://www.dspguru.com/comp.dsp/tricks/alg/fxdatan2.htm

It's basically an approximation using the ratio of the difference and sum of I and Q (or x and y). If you want to compute atan2(x, y), then compute the ratio:

$r={\frac {x-y}{x+y}}$

The phase angle in quadrant I is

$\theta _{1}={\frac {\pi }{4}}-{\frac {\pi }{4r}}$

In quadrant II:

$r={\frac {x+y}{y-x}}$

The phase angle in quadrant II is

$\theta _{2}={\frac {3\pi }{4}}-{\frac {\pi }{4r}}$

The maximum error is about 0.07 rads. This can be improved significantly using:

$\theta _{1}=0.1963r^{3}-0.9817r+{\frac {\pi }{4}}$

$\theta _{2}=0.1963r^{3}-0.9817r+{\frac {3\pi }{4}}$

Guesstimating Inductance of Wire Loops

Here's an interesting article by Marc T. Thompson:

http://members.aol.com/marctt/CV/Abstracts/inductance.htm

It basically says that inductance of a wire is roughly

$0.5-1.0{\frac {\mu H}{m}}$

This simple estimate is surprizingly accurate!

Code Generation

Prefix form

Prefix form, such as Lisp S-expressions, might be more interesting as an intermediate form compared with quads. For the purposes of realization in standard machine architectures, typed S-expressions result in more efficient code. Consider the following forms:

int a, b, c, d;
d = b*b - 4*a*c;

Bytecode would be:

iload b
iload b
imul
iconst 4
iload a
imul
iload c
imul
isub
istore d

Quads:

t0 = b * b
t1 = 4 * a
t2 = t1 * c
t3 = t0 - t2
d = t3

S-expression:

d = (- (* b b) (* 4 a c))

Each function (operator) in the S-expression can implement polymorphic methods:

public abstract Object execute(SExpression args);
public abstract Code emit(SExpression args);

The execute method can be used in interpretation mode, whereas the emit() method could generate machine code for a specific processor. The emit() method is far simpler when compared with a quad based code generator. Further, the emit() method could be tested interactively by generating code in memory and executing it.

The result of emit for the above example would be:

mov r0, b
mul r0, b
mov r1, 4
mul r1, a
mul r1, c
sub r0, r1
store d, r0

Register allocation and assignment are performed using standard techniqes.

Binary files

Binary files are easily manipulated using a generalized schema rather than fine grained classes representing every type of primitive. For example, BCEL and com.madhu.dcg are far more complicated than they need to be. The schema would replace classes as the definition of the binary file. LISP has an advantage in that S-expressions are an excellent structure for representing the schema itself. Something similar can be done with XML, which is far more verbose.

In essence, parsing a binary file results in something like a DOM tree. A simple traversal expression, conceptually similar to XPATH, can be used to access elements within the binary.

An augmented LL grammar should be powerful enough to describe the file format. A lightweight, dynamic LL parser generator would be a good solution. The case where a list of structures is preceded by a length word can be recognized using a hybrid parser that first reads the count and calls the LL parser repeatedly to build a syntax tree. The full grammar is probably not LL.

Prototype Implementation

Develop a simplified, typed LISP-like form supporting only a few types such as int, boolean, and Object. Maybe just start with int. Develop a trivial code generator for IA 32 and evaluate its performance. Madhu 17:13, 3 Apr 2005 (UTC)

NFA based code generator

Given an input sentence consisting of operation tuples:

(operation, addressing-mode, operand1, operand2, ...)

Where:

• operation is an ALU operation, e.g. add, sub, shift, and etc.
• addressing-mode is a combination of register, stack, immediate, or memory
• operandN is a register number, stack offset, memory address, or constant

Define a NFA with rules

(iadd, RR, eax, eax)     genIADD();

genIADD() is an action method called when the rule matches an input sentence. The action method can refer to all instructions matched by the pattern as an array of RTL objects.

The entire permutation of operation and addressing modes is probably not necessary. In most cases, addressing mode is probably the most important field. Consider the case of ALU operations for IA32:

(iadd|isub|ior|iand|ixor, RR, eax-edi, eax-edi)  genALUOp();

This results in only a handful of rules and covers most instructions.

The pattern could include ranges, e.g. [0-7], or, e.g. eax|edx etc. Pattern sequences can coalesce into one machine instruction. This is particulary useful in the case of (add, int, RC, EAX, 1) and conditional branches.

The DFA to accepts the same language is probably very large, so a simple NFA is a better choice.

Pico VM

VM with exactly two instructions:

• Object invoke(Method m, Object[] args)
• void ifTrue(boolean test, Address target)

invoke is an instance method call if args[0] is not null, static method call otherwise. Method arguments and return values could be primitives or reference types stored in registers or local (stack) variables.

An SLR based code generator could match sequences and emit target specific instructions. The rules match on instruction and method signature (method name, argument types, and storage location).

AI

Observing and affecting the physical world is important. Generalizations and formal theories can be developed and confirmed through direct measurement. Once suitable models of the real world are determined, predictions can be made. Prediction, or feed forward control is a key step in AI. Perhaps self awareness is a consequence of accurate feed forward control, e.g. knowing that you have a predictable affect on the real world might be the essence of contiousness.

A very simple form of AI is a feed forward control system that determines the transfer function of the plant by varying a control signal.

Simple LL Parser

Links:

• http://www.cse.buffalo.edu/~drpierce/cse/443S2005/lectures/TopDownParsing.ppt
• http://users.comlab.ox.ac.uk/luke.ong/teaching/moc/pda2up.pdf

• Parsing decisions
  • Which non-terminal to expand?
  • Which grammar rule of a non-terminal to expand?
• Non-deterministic parser
  • Try everything, choose the one that works
• Predictive parsing
  • Look at the input and choose exactly one grammar rule

Models of computation

A simple LL parser can be built for handling text and binary input. Simple rules such as

E -> A (B)*

Can be translated into

A();
while (lookAhead(1) in B.firstSet()) {
    consumeLookAhead(1);
    B();
}

Predicates for counting are useful in binary file parsing:

CP -> count:U16 ( CPEntry ) {count}

This becomes:

count = U16();
for (int i=0; i<count; i+=1) {
    CPEntry();
}

The object model for the parser could look like this:

class Terminal extends Node {
    private NFANode nfaStart;  // regular expression describing this terminal
}

class NonTerminal extends Node {
    private List productions;
    private List firstSet;
    private List followSet;

    private void computeFirst();
    private void computeFollow();
}

It should be possible to directly execute the parser without generating code or tables. Further, the scanner is implicit as a set of NFA nodes in the FIRST and FOLLOW sets for each non-terminal. The parser specification contains embedded regular expressions for each terminal. This eliminates the need for a separate scanner definition. Simple macro substitution could be implemented to avoid duplicating common regular expressions.

The use of embedded regular expressions could yield a context sensitive scanner, which increases the strength of the overall parser.

Metadata

Information about information.

• class -> object
• schema -> document (XML)
• schema -> table (relational database)
• grammar -> language

Class as metadata

A class definition is a tree structure. It can be used as metadata, such as a language grammar. Introspection can be used to create a parser. This has several advantages:

• Compile time syntax and type checking
• Java based actions
• Context sensitive parsing (access to parser engine)