🌕 👶🏽 📊 Implementierung der Minimierung logischer Funktionen durch die Quine \ McCluskey-Methode mit einem unvollständigen Eingabesatz 🐸 🔲 🙉

Dieser Artikel ist bis zu einem gewissen Grad eine Fortsetzung meines Artikels über die Minimierung logischer Funktionen durch die Quine-Mac'Klaski-Methode ( https://habr.com/post/328506 ). Es wurde ein Fall mit vollständig definierten logischen Funktionen betrachtet (obwohl dies nicht direkt darin erwähnt, sondern nur impliziert wurde). In der Realität ist ein solcher Fall ziemlich selten, wenn die Anzahl der Eingabevariablen gering ist. Teilweise oder unvollständig definiert sind logische Funktionen, deren Werte nur für Teil Q aus der Gesamtmenge P = angegeben werden

2^{N}

$2 ^ N$ mögliche Mengen (Terme) ihrer Argumente (Variablen) der Zahl N , dh Q <P. Diese Situation tritt in der Praxis in den meisten Fällen bei der Anwendung von Algorithmen zur Optimierung logischer Funktionen auf. Wenn beispielsweise die Anzahl der Eingabevariablen N = 30 beträgt, was beispielsweise auf den Finanzmärkten üblich ist, sollte das Volumen der Stichprobe für das Eingabetraining in der Größenordnung von liegen

2^{30}

$2 ^ {30}$ >

10^{9}

$10 ^ 9$ einzigartige einzigartige Begriffe. Ein solches Datenarray findet sich nicht in jeder sehr großen Organisation, ganz zu schweigen von Einzelpersonen, das heißt, dies ist bereits die Sphäre von BigData, die Nutzung von Rechenzentren usw.

Daher werden in der Praxis häufig minimierte logische Funktionen nicht einfach aufgrund des Fehlens der erforderlichen Menge an akkumulierten Daten oder aufgrund verschiedener anderer objektiver Gründe (zum Beispiel ist nicht genügend Speicherplatz zum Speichern vorhanden) vollständig bestimmt. Es stellt sich die Frage nach der Möglichkeit der "Umgehung" dieses Problems, wenn ein Algorithmus verwendet wird, der mit einem vollständig definierten Satz von Begriffslogikfunktionen arbeitet, wie beispielsweise aus meinem vorherigen Artikel.

In diesem Fall wird standardmäßig der unvollständige Eingabesatz von Variablen- (Term-) Werten zum vollständigen Wert bestimmt, um ein optimales Ergebnis für den vorhandenen Datensatz zu erhalten. In diesem Fall besteht jedoch ein Problem bei der Aufzählung aller möglichen Varianten zusätzlicher Definitionen, deren Gesamtzahl V = ist

2^{P - Q}

$2 ^ {P-Q}$ Auswahl der besten Option für eine zusätzliche Definition gemäß einem bestimmten Kriterium. Offensichtlich ist für die tatsächlich verwendeten Werte von Q und P die Anzahl der sortierten Optionen für zusätzliche Definitionen astronomisch groß, und dieser Ansatz kann aufgrund des immensen Rechenaufwands in der Praxis nicht implementiert werden.

Daher ist ein anderer Ansatz erforderlich, der die Aufzählung verschiedener Optionen für zusätzliche Definitionen überflüssig macht. Daher ist es notwendig, den ursprünglichen Algorithmus zu modernisieren, der anfänglich nur mit einem vollständig definierten Eingabesatz funktioniert, damit er auch mit einem abgeschnittenen Satz arbeiten kann. Es ist eine solche Implementierung des in diesem Artikel vorgeschlagenen Algorithmus, basierend auf der Tatsache, dass während des Minimierungsprozesses zwei unvollständige Listen von Begriffen gleichzeitig verarbeitet werden, auf denen die Funktion als FALSE (0) und TRUE (1) angegeben wird.

Unter dem Gesichtspunkt des maschinellen Lernens implementiert der Quine-Mac'Klaski-Algorithmus das Lernparadigma mit dem Lehrer, wenn die entsprechenden Ausgabewerte der Zielfunktion gleichzeitig in den Lernprozess (in diesem Fall Minimierung) einbezogen werden. Ich möchte Sie daran erinnern, dass das Funktionsprinzip der grundlegenden Quine-Mac'Klaski-Methode nach der Theorie aus zwei Hauptstufen besteht:

Bühne. Finden aller einfachen LF-Begriffe mithilfe von Kleberegeln (Gesetzen):
a) (A & B)? (A &! B)? A;
b) (A? B) & (A?! B)? A;
Wo ist die logische UND-Verknüpfung? - Operation des logischen "ODER" ;! - Operation der logischen Negation "NICHT". Aus diesen Formeln folgt, dass zwei Terme zusammengeklebt werden, wenn sie sich nur in einer der Positionen der Variablen voneinander unterscheiden. An der Stelle, an der sich die beiden Begriffe voneinander unterscheiden, wird das Zeichen „*“ gesetzt. Somit erweitert sich das geklebte Alphabet im Vergleich zum Original auf drei Werte:
• 0 => falsch;
• 1 => wahr;
• 2 => geklebte Variable (*).
Bühne. Minimierung der Anzahl der eingeklebten Terme, die nach der ersten Stufe erhalten wurden, als Problem beim Finden der optimalen Abdeckung des anfänglichen Satzes von Begriffen mit der Menge Q. Das heißt, da jeder Ausgabeausdruck nur eine bestimmte Teilmenge der Quellausdrücke abdeckt, ist es notwendig, einen minimalen Satz von Ausgabeausdrücken zu wählen, mit denen identifiziert wird Mit ihnen deckten Teilmengen unterschiedlicher Länge im Aggregat alle anfänglichen Eingabebegriffe vollständig ab. Beschichten bedeutet in diesem Fall, dass die bitweise Operation der Disjunktion des Ausgangsterms über den Eingangsterm einen wahren Wert ergab. Angenommen, der ausgegebene geklebte Term hat die folgende Form: 10 * 0110 *.
Dann deckt es den Begriff 10101100 ab:
10 * 0110 * & 10101100 = TRUE
deckt aber nicht den Begriff 00101100 ab:
10 * 0110 * & 00101100 = FALSE
Das heißt, der Eingabeterm und der Ausgang müssen überall zusammenfallen, mit Ausnahme der Positionen, an denen ein "*" - Symbol angezeigt wird. In dieser Position kann die Variable des Eingabeterms einen beliebigen Wert annehmen, da In dieser Position wird die Variable von der Betrachtung ausgeschlossen.

Der Implementierungscode lautet wie folgt (zum Anzeigen klicken):

using System; using System.Collections.Generic; using System.Linq; #region   /// <summary> ///      /// </summary> public abstract class LogicFunction { // ""  public const byte cStarSymb = 2; //    public readonly ICollection<byte[]> Terms = new LinkedList<byte[]>(); //   public abstract bool Calculate(bool[] X); //   public abstract bool Calculate(char[] X); //   public abstract bool Calculate(byte[] X); } /// <summary> ///    /// </summary> public class Dnf : LogicFunction { public static bool Calculate(byte[] X, byte[] term) { bool bResult = true; for (int i = 0; i < term.Length; i++) { if ((term[i] == cStarSymb) || (term[i] == X[i])) continue; bResult = false; break; } return bResult; } public override bool Calculate(byte[] X) { bool bResult = false; foreach (byte[] term in Terms) { bool bTermVal = true; for (int i = 0; i < term.Length; i++) { if ((term[i] >= cStarSymb) || (term[i] == X[i])) continue; bTermVal = false; break; } //bResult |= bTermVal; if (bTermVal) { bResult = true; break; } } return bResult; } public override bool Calculate(char[] X) { bool bResult = false; foreach (byte[] term in Terms) { bool bTermVal = true; for (int i = 0; i < term.Length; i++) { if ((term[i] >= cStarSymb) || (term[i] == (byte)(X[i] == '0' ? 0 : 1))) continue; bTermVal = false; break; } //bResult |= bTermVal; if (bTermVal) { bResult = true; break; } } return bResult; } public override bool Calculate(bool[] X) { bool bResult = false; foreach (byte[] term in Terms) { bool bTermVal = true; for (int i = 0; i < term.Length; i++) { if ((term[i] >= cStarSymb) || ((term[i] != 0) == X[i])) continue; bTermVal = false; break; } //bResult |= bTermVal; if (bTermVal) { bResult = true; break; } } return bResult; } } #endregion /// <summary> ///   /// </summary> public class TreeFuncTerm { /// <summary> ///     /// </summary> public class TreeNodeEnd { } //    private readonly TreeNodeEnd pCommonTreeNodeEnd = new TreeNodeEnd(); //  private readonly object[] rootNode = new object[3]; // ()  private int _rang = 0; public int Rang { get { return _rang; } } //    private int enumerationPos = 0; private object[][] enumerationBuf; //,     private byte[] enumerationTerm; public byte[] EnumerationTerm { get { return enumerationTerm; } } //     private UInt32 _count = 0; public UInt32 Count { get { return _count; } } // public TreeFuncTerm() { Clear(); } //  public void Clear() { _count = 0; _rang = 0; enumerationPos = 0; enumerationBuf = null; enumerationTerm = null; rootNode[0] = rootNode[1] = rootNode[2] = null; } //      public TreeNodeEnd EnumerationInit() { enumerationPos = 0; enumerationTerm = new byte[_rang]; enumerationTerm[0] = 0; enumerationBuf = new object[_rang][]; enumerationBuf[0] = rootNode; //    return EnumerationNextNode(); } //     public TreeNodeEnd EnumerationNextNode() { int iIsNext = (enumerationPos > 0 ? 1 : 0); TreeNodeEnd pRetTreeNode = null; while ((pRetTreeNode == null) && (enumerationPos >= 0)) { object[] pCurrNodes = enumerationBuf[enumerationPos]; object pNextNode = null; int i = enumerationTerm[enumerationPos] + iIsNext; for (; i < 3; i++) if ((pNextNode = pCurrNodes[i]) != null) break; if (pNextNode == null) { //    enumerationPos--; iIsNext = 1; } else { enumerationTerm[enumerationPos] = (byte)i; if (pNextNode is object[]) { //    enumerationPos++; enumerationBuf[enumerationPos] = (object[])pNextNode; enumerationTerm[enumerationPos] = 0; iIsNext = 0; } else //if (pNextNode is TreeNodeEnd) { //   pRetTreeNode = (TreeNodeEnd)pNextNode; } } } return pRetTreeNode; } //     public void AddTerm(byte[] term) { _rang = Math.Max(_rang, term.Length); object[] pCurrNode = rootNode; int iTermLength1 = term.Length - 1; for (int j = 0; j < iTermLength1; j++) { byte cSymb = term[j]; object item = pCurrNode[cSymb]; if (item == null) { item = new object[3]; pCurrNode[cSymb] = item; } pCurrNode = (object[])item; } if (pCurrNode[term[iTermLength1]] == null) { //    pCurrNode[term[iTermLength1]] = pCommonTreeNodeEnd; _count++; } } //      public TreeNodeEnd Remove(byte[] term) { int iTermLength1 = term.Length - 1; object[] pCurrNode = rootNode; for (int i = 0; i < iTermLength1; i++) { pCurrNode = (object[])pCurrNode[term[i]]; if (pCurrNode == null) break; } TreeNodeEnd pRemovedNode = null; if (pCurrNode != null) { //      pRemovedNode = (TreeNodeEnd)pCurrNode[term[iTermLength1]]; if (pRemovedNode != null) { //     pCurrNode[term[iTermLength1]] = null; // -  _count--; } } return pRemovedNode; } //     public bool Contains(byte[] term) { object pCurrNode = rootNode; foreach (byte cSymb in term) { pCurrNode = ((object[])pCurrNode)[cSymb]; if (pCurrNode == null) break; } return ((pCurrNode != null) && (pCurrNode is TreeNodeEnd)); } } /// <summary> ///     ---- /// </summary> public class Quine_McCluskey { //    private readonly Dnf _result = new Dnf(); public Dnf Result { get { return _result; } } //    private readonly Dnf _resultNeg = new Dnf(); public Dnf ResultNeg { get { return _resultNeg; } } //     private static void Skleivanie(TreeFuncTerm X1Tree, TreeFuncTerm X2Tree, TreeFuncTerm NegativTree, IEnumerable<byte[]> InpNegTerms, Dictionary<int, LinkedList<byte[]>> OutResult, int iLevel) { LinkedList<byte[]> OutR = new LinkedList<byte[]>(); if (OutResult != null) OutResult.Add(iLevel, OutR); bool IsVirtSkleivOn = ((NegativTree != null) && (InpNegTerms != null) && (InpNegTerms.Count() != 0)); for (TreeFuncTerm.TreeNodeEnd x1 = X1Tree.EnumerationInit(); x1 != null; x1 = X1Tree.EnumerationNextNode()) { bool bIsSkleiv = false; byte[] pCurrTerm = X1Tree.EnumerationTerm; for (int iPos = 0; iPos < pCurrTerm.Length; iPos++) { byte cSymbSav = pCurrTerm[iPos]; if (cSymbSav == LogicFunction.cStarSymb) continue; //      pCurrTerm[iPos] = (byte)(1 - cSymbSav); if (X1Tree.Contains(pCurrTerm)) { bIsSkleiv = true; //,         if (cSymbSav == 1) { pCurrTerm[iPos] = LogicFunction.cStarSymb; //  X2Tree.AddTerm(pCurrTerm); } } //    ,    NegativTree else if (IsVirtSkleivOn && !NegativTree.Contains(pCurrTerm)) { bool bIsNotCanAdd = false; pCurrTerm[iPos] = LogicFunction.cStarSymb; //  foreach (byte[] NegTerm in InpNegTerms) { if (bIsNotCanAdd = Dnf.Calculate(NegTerm, pCurrTerm)) break; } if (!bIsNotCanAdd) { bIsSkleiv = true; X2Tree.AddTerm(pCurrTerm); } } pCurrTerm[iPos] = cSymbSav; } //    ,       if (!bIsSkleiv) OutR.AddLast((byte[])pCurrTerm.Clone()); } } //     private static UInt64 GetTermCode(byte[] pTerm) { UInt64 iMultip = 1, iCode = 0; for (int i = 0; i < pTerm.Length; i++) { iCode += (iMultip * pTerm[i]); iMultip *= 3; } return iCode; } //     private static byte[] GetTermByCode(UInt64 iCode, int iTermLength, byte[] pTerm = null) { if (pTerm == null) pTerm = new byte[iTermLength]; int iCounter = 0; while (iCode != 0) { pTerm[iCounter++] = (byte)(iCode % 3); iCode /= 3; } while (iCounter < iTermLength) pTerm[iCounter++] = 0; return pTerm; } //     private static void Skleivanie(ICollection<UInt64> X1Tree, ICollection<UInt64> X2Tree, ICollection<UInt64> NegativTree, IEnumerable<byte[]> InpNegTerms, Dictionary<int, LinkedList<byte[]>> OutResult, int iLevel, int iTermLength) { LinkedList<byte[]> OutR = new LinkedList<byte[]>(); if (OutResult != null) OutResult.Add(iLevel, OutR); byte[] pCurrTerm = new byte[iTermLength]; bool IsVirtSkleivOn = ((NegativTree != null) && (InpNegTerms != null) && (InpNegTerms.Count() != 0)); foreach (UInt64 x1 in X1Tree) { GetTermByCode(x1, iTermLength, pCurrTerm); bool bIsSkleiv = false; UInt64 iMultip = 1; for (int iPos = 0; iPos < iTermLength; iPos++) { byte cSymbSav = pCurrTerm[iPos]; //(byte)((x1 / iMultip) % 3); if (cSymbSav != LogicFunction.cStarSymb) { UInt64 iCode = (cSymbSav == 0 ? x1 + iMultip : x1 - iMultip); //      if (X1Tree.Contains(iCode)) { bIsSkleiv = true; //,         if (cSymbSav == 1) { X2Tree.Add(x1 + iMultip); } } //    ,    NegativTree else if (IsVirtSkleivOn && !NegativTree.Contains(iCode)) { bool bIsNotCanAdd = false; pCurrTerm[iPos] = LogicFunction.cStarSymb; //  foreach (byte[] NegTerm in InpNegTerms) { if (bIsNotCanAdd = Dnf.Calculate(NegTerm, pCurrTerm)) break; } pCurrTerm[iPos] = cSymbSav; if (!bIsNotCanAdd) { bIsSkleiv = true; X2Tree.Add(x1 + (byte)(LogicFunction.cStarSymb - cSymbSav) * iMultip); } } } iMultip *= 3; } //    ,       if (!bIsSkleiv) OutR.AddLast((byte[])pCurrTerm.Clone()); } } //      //       private static void DeleteDublicatingTerms(IEnumerable<byte[]> InX1, ICollection<UInt64> OutX2Tree) { OutX2Tree.Clear(); foreach (byte[] x1 in InX1) { UInt64 iCode = GetTermCode(x1); if (OutX2Tree.Contains(iCode)) continue; OutX2Tree.Add(iCode); } } //      //       private static void DeleteDublicatingTerms(IEnumerable<byte[]> InX1, TreeFuncTerm OutX2Tree) { OutX2Tree.Clear(); foreach (byte[] x1 in InX1) OutX2Tree.AddTerm(x1); } //    private static bool IsEqualTerms(byte[] pTermC, byte[] pTermB) { if ((pTermC == null) || (pTermB == null) || (pTermC.Length != pTermB.Length)) return false; bool bIsEqual = false; int iLength = Math.Min(pTermC.Length, pTermB.Length); for ( int i = 0; i < iLength; i++) { if (!(bIsEqual = (pTermB[i] == pTermC[i]))) break; } return bIsEqual; } //            private static void ReduceRedundancyTerms(LinkedList<byte[]> InpTerms, Dictionary<int, LinkedList<byte[]>> SkleivTerms, ICollection<byte[]> ResultTerms) { if ((InpTerms == null) || (SkleivTerms == null) || (ResultTerms == null)) return; //   ResultTerms.Clear(); //        ,    Dictionary<byte[], HashSet<byte[]>> Outputs2Inputs = new Dictionary<byte[], HashSet<byte[]>>(); //        ,    Dictionary<byte[], HashSet<byte[]>> Inputs2Outputs = new Dictionary<byte[], HashSet<byte[]>>(); //    foreach (int iLevel in SkleivTerms.Keys.OrderByDescending(p => p).AsEnumerable()) { //       foreach (byte[] outTerm in SkleivTerms[iLevel]) { //  ,      term HashSet<byte[]> InpTermsLst = new HashSet<byte[]>(); //     foreach (byte[] inpTerm in InpTerms) { if (Dnf.Calculate(inpTerm, outTerm)) { InpTermsLst.Add(inpTerm); if (!Inputs2Outputs.ContainsKey(inpTerm)) Inputs2Outputs.Add(inpTerm, new HashSet<byte[]>()); Inputs2Outputs[inpTerm].Add(outTerm); } } Outputs2Inputs.Add(outTerm, InpTermsLst); } } //      -    Inputs2Outputs = Inputs2Outputs.OrderBy(p => p.Value.Count).ToDictionary(p => p.Key, v => v.Value); //   ,   -    while (Inputs2Outputs.Count > 0) { byte[] outTerm = Inputs2Outputs.First().Value.OrderByDescending(q => Outputs2Inputs[q].Count()).First(); ResultTerms.Add(outTerm); foreach (byte[] inpTerm in Outputs2Inputs[outTerm].ToArray()) { foreach (byte[] outTerm2Del in Inputs2Outputs[inpTerm]) Outputs2Inputs[outTerm2Del].Remove(inpTerm); Inputs2Outputs.Remove(inpTerm); } } } //    public static void LogicFuncMinimize(IEnumerable<byte[]> PositivTerms, ICollection<byte[]> OutPos, IEnumerable<byte[]> NegativTerms, ICollection<byte[]> OutNeg) { int iTotalLevels = (PositivTerms.Count() > 0 ? PositivTerms.First().Length : (NegativTerms != null && NegativTerms.Count() > 0 ? NegativTerms.First().Length : 0)); Dictionary<int, LinkedList<byte[]>> SkleivPosTerms = new Dictionary<int, LinkedList<byte[]>>(iTotalLevels); Dictionary<int, LinkedList<byte[]>> SkleivNegTerms = new Dictionary<int, LinkedList<byte[]>>(iTotalLevels); LinkedList<byte[]> InpPosTerms = new LinkedList<byte[]>(); LinkedList<byte[]> InpNegTerms = new LinkedList<byte[]>(); if (iTotalLevels < 40) { HashSet<UInt64> X1PositivTree = new HashSet<UInt64>(); DeleteDublicatingTerms(PositivTerms, X1PositivTree); HashSet<UInt64> X1NegativTree = null; if (NegativTerms != null) { X1NegativTree = new HashSet<UInt64>(); DeleteDublicatingTerms(NegativTerms, X1NegativTree); //        foreach(UInt64 iNumb in X1PositivTree.Intersect(X1NegativTree)) { // -    X1   NegativTerms int iPos_Count = PositivTerms.Count(p => GetTermCode(p) == iNumb); int iNeg_Count = NegativTerms.Count(p => GetTermCode(p) == iNumb); if (iPos_Count > iNeg_Count) { X1NegativTree.Remove(iNumb); } else if (iPos_Count < iNeg_Count) { X1PositivTree.Remove(iNumb); } else //if (iPos_Count == iNeg_Count) { X1PositivTree.Remove(iNumb); X1NegativTree.Remove(iNumb); } } //           foreach (UInt64 code in X1NegativTree) { InpNegTerms.AddLast(GetTermByCode(code, iTotalLevels)); } } //          foreach (UInt64 code in X1PositivTree) { InpPosTerms.AddLast(GetTermByCode(code, iTotalLevels)); } int iLevelCounter = 0; //        while ((X1PositivTree.Count != 0) && (iLevelCounter < iTotalLevels)) { HashSet<UInt64> X2PositivTree = new HashSet<UInt64>(); Skleivanie(X1PositivTree, X2PositivTree, X1NegativTree, InpNegTerms, SkleivPosTerms, iLevelCounter, iTotalLevels); if ((X1NegativTree != null) && (X1NegativTree.Count != 0)) { HashSet<UInt64> X2NegativTree = new HashSet<UInt64>(); Skleivanie(X1NegativTree, X2NegativTree, X1PositivTree, InpPosTerms, SkleivNegTerms, iLevelCounter, iTotalLevels); //   X1NegativTree.Clear(); X1NegativTree = X2NegativTree; } //   X1PositivTree.Clear(); X1PositivTree = X2PositivTree; iLevelCounter++; GC.Collect(); } } else { TreeFuncTerm X1PositivTree = new TreeFuncTerm(); DeleteDublicatingTerms(PositivTerms, X1PositivTree); TreeFuncTerm X1NegativTree = null; if (NegativTerms != null) { X1NegativTree = new TreeFuncTerm(); DeleteDublicatingTerms(NegativTerms, X1NegativTree); //         for (TreeFuncTerm.TreeNodeEnd x1 = X1PositivTree.EnumerationInit(); x1 != null; x1 = X1PositivTree.EnumerationNextNode()) { if (!X1NegativTree.Contains(X1PositivTree.EnumerationTerm)) continue; // -    PositivTerms   NegativTerms int iPos_Count = PositivTerms.Count(p => IsEqualTerms(p, X1PositivTree.EnumerationTerm)); int iNeg_Count = NegativTerms.Count(p => IsEqualTerms(p, X1PositivTree.EnumerationTerm)); if (iPos_Count > iNeg_Count) { X1NegativTree.Remove(X1PositivTree.EnumerationTerm); } else if (iPos_Count < iNeg_Count) { X1PositivTree.Remove(X1PositivTree.EnumerationTerm); } else //if (iPos_Count == iNeg_Count) { X1PositivTree.Remove(X1PositivTree.EnumerationTerm); X1NegativTree.Remove(X1PositivTree.EnumerationTerm); } } //           for (TreeFuncTerm.TreeNodeEnd x1 = X1NegativTree.EnumerationInit(); x1 != null; x1 = X1NegativTree.EnumerationNextNode()) { InpNegTerms.AddLast((byte[])X1NegativTree.EnumerationTerm.Clone()); } } //          for (TreeFuncTerm.TreeNodeEnd X1Term = X1PositivTree.EnumerationInit(); X1Term != null; X1Term = X1PositivTree.EnumerationNextNode()) { InpPosTerms.AddLast((byte[])X1PositivTree.EnumerationTerm.Clone()); } int iLevelCounter = 0; //        while ((X1PositivTree.Count != 0) && (iLevelCounter < iTotalLevels)) { TreeFuncTerm X2PositivTree = new TreeFuncTerm(); Skleivanie(X1PositivTree, X2PositivTree, X1NegativTree, InpNegTerms, SkleivPosTerms, iLevelCounter); if ((X1NegativTree != null) && (X1NegativTree.Count != 0)) { TreeFuncTerm X2NegativTree = new TreeFuncTerm(); Skleivanie(X1NegativTree, X2NegativTree, X1PositivTree, InpPosTerms, SkleivNegTerms, iLevelCounter); //   X1NegativTree.Clear(); X1NegativTree = X2NegativTree; } //   X1PositivTree.Clear(); X1PositivTree = X2PositivTree; iLevelCounter++; GC.Collect(); } } //       ReduceRedundancyTerms(InpPosTerms, SkleivPosTerms, OutPos); //       ReduceRedundancyTerms(InpNegTerms, SkleivNegTerms, OutNeg); } //  public void Start(IEnumerable<byte[]> TermsInput) { LogicFuncMinimize(TermsInput, _result.Terms, null, null); } //  public void Start(IEnumerable<byte[]> TermsInput, IEnumerable<byte[]> NegativTerms) { LogicFuncMinimize(TermsInput, _result.Terms, NegativTerms, _resultNeg.Terms); } //  public void Start(IEnumerable<char[]> TermsInput) { Start(TermsInput.Select(t => t.Select(p => (byte)(p == '0' ? 0 : 1)).ToArray())); } //  public void Start(IEnumerable<char[]> TermsInput, IEnumerable<char[]> NegativTerms) { Start(TermsInput.Select(t => t.Select(p => (byte)(p == '0' ? 0 : 1)).ToArray()), NegativTerms.Select(t => t.Select(p => (byte)(p == '0' ? 0 : 1)).ToArray())); } //  public void Start(IEnumerable<bool[]> TermsInput) { Start(TermsInput.Select(t => t.Select(p => (byte)(p ? 1 : 0)).ToArray())); } //  public void Start(IEnumerable<bool[]> TermsInput, IEnumerable<bool[]> NegativTerms) { Start(TermsInput.Select(t => t.Select(p => (byte)(p ? 1 : 0)).ToArray()), NegativTerms.Select(t => t.Select(p => (byte)(p ? 1 : 0)).ToArray())); } public void PrintResult() { Console.WriteLine("--------Otvet-------"); char[] pTermSymbs = new char[] { '0', '1', '*' }; foreach (byte[] Term in _result.Terms) { for (int j = 0; j < Term.Length; j++) { Console.Write(pTermSymbs[Term[j]].ToString() + " "); } Console.WriteLine(); } } }

Die Quine_McCluskey-Klasse ist eine Implementierung dieses Algorithmus, der andere Klassen und Schnittstellen verwendet: Dnf, TreeNodeBase, TreeNodeMiddle, TreeNodeEnd, TreeFuncTerm. Um die Optimierung zu starten, müssen Sie eine der überladenen Start-Methoden aufrufen, die die LogicFuncMinimize-Funktion aufruft, wobei tatsächlich der Minimierungsalgorithmus implementiert ist. Der Minimierungsmechanismus ist in zwei Versionen implementiert:
• Verwenden des .NET SortedSet-Containers zum Speichern und Suchen von Begriffen.
• ohne Verwendung von .NET-Containern, die auf dem ternären TreeFuncTerm-Baum basieren.

In Bezug auf die Geschwindigkeit sind diese beiden Optionen ungefähr gleich (bei .NET-Containern vielleicht etwas schneller, aber nicht immer), aber die Notwendigkeit, TreeFuncTerm zu implementieren, beruht auf mehreren Faktoren:
• Die erste Option, die auf 64-Bit-Integer-Hashcodes und einer Suche im SortedSet .NET-Wörterbuch basiert, funktioniert nur mit der Anzahl der Eingabevariablen in Begriffen bis zu 40 korrekt. wird für den Containerbetrieb verwendet. Da ternäre Logik innerhalb des Algorithmus in geklebten Begriffen verwendet wird, ist der Maximalwert des Hash-Codes bei einer Anzahl von Eingangsvariablen gleich 41

3^{41}

$3 ^ {41}$ überschreitet bereits den Maximalwert

2^{64}

$2 ^ {64}$ -1, die in eine 64-Bit-Variable geschrieben werden kann. Bei mehr Variablen wird eine Option verwendet, die auf dem ternären Suchbaum TreeFuncTerm des Autors basiert.
• Es ist erforderlich, den Betrieb der Implementierung auf .NET-Containern mit einer anderen, davon unabhängigen Implementierung zu überprüfen.
• Sie benötigen lediglich eine Option, die frei von .NET-Containern ist und problemlos auf Plattformen implementiert werden kann, auf denen keine .NET-Plattform vorhanden ist (z. B. in Mikrocontrollern, FPGAs usw.).
Die Operation des TreeFuncTerm-Suchbaums basiert auf der Konfiguration von Links zu den Klassen TreeNodeMiddle und TreeNodeEnd, die Implementierungen der TreeNodeBase-Schnittstelle sind. Die TreeNodeMiddle-Klasse ist ein Zwischenknoten des Baums, und die TreeNodeEnd-Klasse ist das Blattende des Baums. Mit den Funktionen EnumerationInit () und EnumerationNextNode () wird im Baum ein nicht rekursiver Mechanismus zum Auflisten aller Blattblätter von TreeNodeEnd implementiert. Die Funktion EnumerationInit () initialisiert die Aufzählung und gibt das erste Blatt im Baum zurück. Die Funktion EnumerationNextNode () gibt das nächste Baumblatt oder NULL zurück, wenn keine Blätter mehr für die Auswahl vorhanden sind. Darüber hinaus ist die interne Hilfsstruktur EnumerationTerm, die die Position des Such-Cursors innerhalb des Baums widerspiegelt, auch der Begriff Code des gefundenen Blattes in der ternären Logik {0,1,2}. Es ist zu beachten, dass die Reihenfolge der Auswahl der Blätter aus dem Baum nicht mit der Reihenfolge ihrer Hinzufügung übereinstimmt.

Der Algorithmus für funktionale Zwecke kann in drei Stufen unterteilt werden.

Vorbereitung. Um das obige Problem des Eliminierens der Aufzählung von Optionen für zusätzliche Definitionen in der betrachteten Implementierung zu lösen, erhält die Eingabe des Algorithmus in die LogicFuncMinimize-Funktion zwei Anfangsdatensätze PositivTerms und NegativTerms, für die die optimierte Funktion wahre (TRUE, 1) bzw. falsche (FALSE, 0) Werte akzeptiert. Zunächst werden diese Listen auf Konsistenz der Quelldaten überprüft. Es ist erforderlich, dass jeder Datensatz garantiert nur eindeutige Begriffe enthält, die nur in einer der Listen vorhanden sind. Um dies zu gewährleisten, wird jeder einzelne Eingabebegriff gescannt und die Anzahl der Einträge in jeder der Quelllisten gefunden. Wenn der Begriff in beiden Listen vorkommt, bleibt er nur in der Liste, in der er mehr vorkommt, und wird aus der anderen Liste gelöscht. Wenn der Begriff in jeder der Listen gleich häufig vorkommt, wird er aus beiden Listen entfernt, wodurch die Eindeutigkeit sichergestellt wird.
Verklebung. Als nächstes wird ein iterativer Zyklus zum Kleben von Eingabeterms durchgeführt. Bei jeder Iteration wird geklebt ein Vorzeichen * der geklebten Position hinzugefügt. Daher kann die Anzahl der Iterationen nicht größer sein als die Anzahl der Variablen N. Im Gegensatz zur vorherigen Implementierung kann die Skleivanie-Funktion zum Kleben von Eingabebegriffen nicht nur mit Begriffen aus ihrer Liste geklebt werden, sondern auch, wenn kein Begriff mit einem Unterschied vorhanden ist, auch mit den sogenannten "virtuellen" Begriffen. Mit "virtuellen" Begriffen meinen wir künstlich definierte Begriffe, die in keiner der Begriffslisten eines Satzes der aktuellen Ebene enthalten sind. Das Kleben ist jedoch nur möglich, wenn der „virtuelle“ Begriff nicht einen einzelnen Begriff des ursprünglichen Satzes der gegenüberliegenden Liste abdeckt.
Die Skleivanie-Funktion wird aufgerufen, um Listen bei jeder Iteration zweimal zu verarbeiten, so dass beim ersten Aufruf die Bedeutung der Verwendung der Listen PositivTerms und NegativTerms mit ihrem tatsächlichen Inhalt übereinstimmt, und beim zweiten Aufruf werden die Listen PositivTerms und NegativTerms in Bezug auf die Verwendung ausgetauscht, d. H. Die PositivTerms-Liste enthält negative Begriffe und die NegativTerms-Liste enthält positive Begriffe:
Skleivanie (X1PositivTree, ..., X1NegativTree, ..., SkleivTerms, ...);
Skleivanie (X1NegativTree, ..., X1PositivTree, ..., null, ...);
Somit erfolgt eine gleichzeitige wechselseitige Verklebung der Begriffe zweier Listen.
Wenn es für den Begriff keinen anderen Begriff gibt, der sich von ihm nur in einer Position unterscheidet, weder real noch virtuell, dh der Begriff bleibt mit niemandem zusammen, dann wird er als eines der Ergebnisse von Schritt 1 des Algorithmus angesehen, er wird von der weiteren Arbeit darin ausgeschlossen und handelt zur Eingabe von Stufe 2 des Algorithmus, der in der ReduceRedundancyTerms-Prozedur implementiert ist. Nicht geklebte Begriffe kommen nur bei diesem Aufruf der Skleivanie-Funktion zur Ausgabe des Algorithmus, für die die Bedeutung der Verwendung der Listen PositivTerms und NegativTerms mit ihrer tatsächlichen Füllung übereinstimmt, d. H. Beim ersten Aufruf.
Abkürzung. Redundante geklebte Terme werden in ReduceRedundancyTerms unter Verwendung eines Algorithmus verworfen, um das Problem der Abdeckung der ursprünglichen Menge mit Teilmengen variabler Länge näherungsweise zu lösen. Die Abdeckung, die der kürzesten nahe kommt, wird durch den Algorithmus zum Konvertieren der Abdeckungstabelle (TP) bereitgestellt, der auf der Methode „Minimum Column - Maximum Row“ basiert (siehe hier http://www.studfiles.ru/preview/5175815/page:4 ). .
Die ungefähre Logik seiner Arbeit lautet wie folgt:
0. Die ursprüngliche Tabelle wird als das aktuell transformierte TP betrachtet. Der Satz von Abdeckungslinien ist leer.
1. Die Spalte mit den wenigsten Einheiten wird in der aktuellen Tabelle hervorgehoben. Unter den Zeilen mit Einheiten in dieser Spalte wird eine mit der größten Anzahl von Einheiten hervorgehoben. Diese Zeile ist in der Abdeckung enthalten. Die aktuelle Tabelle wird reduziert, indem alle Spalten gelöscht werden, in denen die ausgewählte Zeile eine Einheit enthält.
2. Wenn die Tabelle keine durchgestrichenen Spalten enthält, wird Schritt 1 ausgeführt, andernfalls wird die Abdeckung erstellt. Hinweis: Bei der Berechnung der Anzahl der Einheiten in einer Zeile werden Einheiten in nicht markierten Spalten berücksichtigt.
Dieser Algorithmus arbeitet schnell genug und liefert ein nahezu optimales Ergebnis.
Um die Funktionsweise des Algorithmus zu testen, wird vorgeschlagen, die Testfunktion TestQuineMcCluskeyRandomPart zu verwenden, die aus der Gesamtheit der möglichen Begriffe besteht $2 ^ N$ wählt zufällig nur den angegebenen Teil 0 <dPart <= 1 aus (ist ein Parameter der Funktion), für den eine Optimierung durchgeführt wird. Mit dem Parameter dPart <1 wird ein abgeschnittener Satz von Eingabeausdrücken erhalten, und mit dPart = 1 wird ein vollständiger Satz von Eingabedaten erhalten.

TestQuineMcCluskeyRandomPart (zum Anzeigen klicken)

 public static void TestQuineMcCluskeyRandomPart(int iVariableAmount, double dPart=1) { if (dPart < 0) throw new ArgumentException(" dPart    0   1"); if (dPart > 1) dPart = 1; //   ulong iTotalCombines = (ulong)1 << iVariableAmount; LinkedList<byte[]> pTrueCol = new LinkedList<byte[]>(); LinkedList<byte[]> pFalseCol = new LinkedList<byte[]>(); HashSet<ulong> pUsedTerms = new HashSet<ulong>(); Random rnd = new Random(); byte[] buf = new byte[8]; while (pUsedTerms.LongCount() < (iTotalCombines * dPart)) { rnd.NextBytes(buf); ulong iCurValue = (ulong)BitConverter.ToInt64(buf, 0) % iTotalCombines; if (pUsedTerms.Contains(iCurValue)) { //  -     do { iCurValue = ++iCurValue % iTotalCombines; } while (pUsedTerms.Contains(iCurValue)); } pUsedTerms.Add(iCurValue); byte[] sLine = new byte[iVariableAmount]; for (int i = 0; i < iVariableAmount; i++) { sLine[i] += (byte)(iCurValue % 2); iCurValue >>= 1; } if (rnd.Next(2) != 0) { pTrueCol.AddLast(sLine); } else { pFalseCol.AddLast(sLine); } } //   DateTime DtStart = DateTime.Now; Console.WriteLine(" - " + DtStart.ToLongTimeString()); Quine_McCluskey Logic = new Quine_McCluskey(); Logic.Start(pTrueCol, pFalseCol); DateTime DtEnd = DateTime.Now; Logic.PrintResult(); Console.WriteLine(" - " + DtStart.ToLongTimeString()); Console.WriteLine(" - " + DtEnd.ToLongTimeString()); TimeSpan Elapsed = DtEnd - DtStart; Console.WriteLine(" - " + String.Format("{0:00}:{1:00}:{2:00}", Elapsed.Hours, Elapsed.Minutes, Elapsed.Seconds)); //  int iErrorsCounter = 0; foreach (byte[] kvp in pTrueCol) { if (Logic.Result.Calculate(kvp) != true) iErrorsCounter++; } foreach (byte[] kvp in pFalseCol) { if (Logic.Result.Calculate(kvp) != false) iErrorsCounter++; } Console.WriteLine("-   = " + pUsedTerms.Count); Console.WriteLine("-   = " + Logic.Result.Terms.Count); Console.WriteLine("-  = " + iErrorsCounter); Console.ReadLine(); }

Als Ergebnis der Testfunktion werden die Anzahl der Terme in der minimalen disjunktiven Normalform und die Anzahl der Fehler berechnet, die sie mit dem ursprünglichen Satz von Termen abdecken.

Abschließend möchte ich darauf hinweisen, dass sich diese Implementierung des Algorithmus in der Praxis als wirksames und zuverlässiges Mittel zur Minimierung der logischen Funktionen erwiesen hat, die durch zwei unvollständige Sätze von Begriffen definiert sind, für die die logische Funktion TRUE- bzw. FALSE-Werte annimmt. Natürlich kann diese Implementierung auch in der klassischen Form im Fall einer vollständig definierten logischen Eingabefunktion verwendet werden, wenn nur die eine oder andere Liste von Begriffen eingegeben wird. Als Nachteil muss in der Skleivanie-Funktion überprüft werden, dass bei jeder Iteration des Algorithmus für jeden virtuellen Term der gesamten Liste der Quellterme keine Abdeckungsfehler vorliegen, was zu erheblichen Zeitkosten bei einer großen Anzahl von Eingabebegriffen führt.

Implementierung der Minimierung logischer Funktionen durch die Quine \ McCluskey-Methode mit einem unvollständigen Eingabesatz

More articles: