Net-OnlineCode

 view release on metacpan or  search on metacpan

lib/Net/OnlineCode/Bones.pm  view on Meta::CPAN

In my code, the propagation rule is handled in a routine called
resolve().

=head2 Cascades

When matched, the propagation rule solves one extra node somewhere to
the left of the starting node. In the algebraic interpretation, I
talked about substituting a newly-solved variable into all other
equations where the variable appeared. There is an analogous procedure
in the graph-based implementation, which is implemenented in the
cascade() routine.

For the sake of discussion, let's assume that the message block M was
solved by the propagation rule and that it had the solution:

 M <- A xor C

To simulate substituting M into all other equations where it appears,
we need to work backwards (from left to right) from node M and see if
any of those nodes now match the propagation rule. Since there will be
one rightward edge in the graph from that node for each equation the
left node appears in, this effectively reaches all equations that
could could become solvable.

In the case where the left node which has become solved is an
auxiliary block, the cascade() routine also queues up the auxiliary
node itself for checking the propagation rule.

=head2 Special handling for auxiliary nodes

Although in theory the propagation rule could be applied to unsolved
auxiliary nodes, in practice this has proved troublesome, so I have
not implemented it. Instead I have implemented a special "auxiliary
rule" that gives comparable results.

Recall that the propagation rule works with a single known node on the

lib/Net/OnlineCode/Bones.pm  view on Meta::CPAN

Initially, each auxiliary block will be composed of some number of
message blocks:

 aux   = msg   xor  msg   xor ...
    x       i          j

When the last unsolved message block on the right becomes solved then
this equation has no more unknowns apart from the aux block
itself. Therefore, it can be marked as solved (with the above
solution) and we can cascade up from that aux block to see if it
solves any more equations.

=head2 Optimising by tracking counts of unsolved left nodes

When aux or check nodes are created, the number of unknown/unsolved
edges that they are comprised of is calculated. Whenever a node
becomes solved, each of the nodes that include that node in its list
of edges has their unsolved count decremented.

This improves performance by avoiding having to scan the node's full

lib/Net/OnlineCode/GraphDecoder.pm  view on Meta::CPAN

  # mark node as pending resolution
  push @{$self->{unresolved}}, $node;

  # return index of newly created node
  return $node;

}

# Graph resolution. Resolution of the graph has a "downward" part
# (resolve()) where nodes with one unsolved edge solve a message or
# aux block, and an upward part (cascade()) that works up from a
# newly-solved node.

# helper function
sub apply_solution {

  my ($self, $node, $bone);



}

# Work up from a newly-solved block, potentially doing up-propagation
# rule
sub cascade {
  my ($self,$node) = @_;

  my $mblocks  = $self->{mblocks};
  my $ablocks  = $self->{ablocks};
  my $coblocks = $mblocks + $ablocks;
  my $pending  = $self->{unresolved};

  my @upper = keys %{$self->{bottom}->[$node]};

  if (DEBUG) {
    if (@upper) {
      print "Solved node $node cascades to nodes " . (join " ", @upper)
	. "\n\n";
    } else {
      print "Solved node $node has no cascade\n\n";
    }
  }

  # update the count of unsolved edges and maybe solve aux blocks
  for my $to (@upper) {
    print "Decrementing unknowns count for block $to\n" if DEBUG;
    ($self->{unknowns}->[$to - $mblocks])--;
    
  }
  push @$pending, @upper;

lib/Net/OnlineCode/GraphDecoder.pm  view on Meta::CPAN

      for ($min .. $max) {
	my $lower = $bone->[$_];
	die "Tried to delete non-existent up edge\n" if ASSERT and
	  !exists($self->{bottom}->[$lower]->{$from});
	delete $self->{bottom}->[$lower]->{$from};
      }

      $self->{top}->[$from - $mblocks] = undef;
      
      push @newly_solved, $bone;
      cascade($self, $from);

    } elsif ($unknowns == 1) {

      # Propagation rule matched (one unknown down edge)

      # resolve() only solves a node if the upper node itself is solved.
      # cascade() will handle the case of solving an unsolved aux block
      # by solving its last unsolved message block (upward propagation)


      if ($from < $coblocks and !$solved) {
	print "Skipping down propagation rule on unsolved aux\n" if DEBUG;
	next;
      }

      # pull out the unknown node
      if ($solved) {

lib/Net/OnlineCode/GraphDecoder.pm  view on Meta::CPAN

	  $self->{done} = 1;
	  # comment out next two lines to continue decoding just in
	  # case there's a bug later
	  @$pending = ();
	  last;                 # finish searching
	}
      } else {
	print "Solved auxiliary block $to completely\n" if DEBUG;
	push @$pending, $to;
      }
      cascade($self, $to);
    } else {
      next;			# go to next pending
    }

    return ($self->{done}, @newly_solved) if STEPPING;

  }

  return ($self->{done}, @newly_solved);