PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Powiadomienia systemowe
  • Sesja wygasła!
  • Sesja wygasła!

Znaleziono wyników: 15

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  Boolean functions
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available Novel method to simplify Boolean functions
Prasad V. C.
Automatyka / Automatics
|
2018
|
Vol. 22, no. 2
29--40
EN
Most methods for determining the prime implicants of a Boolean function depend on the minterms of the function. Deviating from this philosophy, this paper presents a method that dependson maxterms (the minterms of the complement of the function) for this purpose. Normally, maxterms are used to get prime implicates and not prime implicants. It is shown that all prime implicants of a Boolean function can be obtained by expanding and simplifying any product of sums form of the function appropriately. No special form of the product of the sums is required. What is more, prime implicants can generally be generated from any form of the function by converting it into a POS using well-known techniques. The prime implicants of a product of Boolean functions can be obtained from the prime implicants of individual Boolean functions. This allows us to handle big functions by breaking them into the products of smaller functions. A simple method is presented to obtain one minimal set of prime implicants from all prime implicants without using minterms. Similar statements also hold for prime implicates. In particular, all prime implicates can be obtained from any sum of a products form.Twelve variable examples are solved to illustrate the methods.
PL
Większość metod wyznaczania implikantów prostych funkcji boolowskiej wykorzystuje mintermy funkcji. Niniejszy artykuł prezentuje odmienną metodę, która stosuje do tego celu makstermy (mintermy dopełnienia funkcji). Jest to podejście niestandardowe, gdyż zazwyczaj na podstawie makstermów uzyskuje się implicenty proste, a nie implikanty proste. W artykule pokazano, że wszystkie implikanty proste funkcji boolowskiej mogą być otrzymane przez odpowiednie rozwinięcie i uproszczenie funkcji podanej w dowolnej postaci typu iloczyn sum. Nie jest przy tym wymagana żadna szczególna postać tego iloczynu. Co więcej, implikanty proste mogą być zwykle utworzone na podstawie funkcji w dowolnej postaci, przez przekształcenie jej do postaci typu iloczyn sum z wykorzystaniem znanych metod. Implikanty proste iloczynu funkcji boolowskich można uzyskać z implikantów prostych poszczególnych funkcji. To pozwala operować na dużych funkcjach przez rozbicie ich na iloczyn mniejszych. Artykuł pokazuje prostą metodę uzyskania jednego zbioru minimalnego implikantów prostych na podstawie zbioru wszystkich implikantów prostych bez korzystania z mintermów. Podobne stwierdzenia mają zastosowanie także w przypadku implicentów prostych. W szczególności, wszystkie implicenty proste mogą być otrzymane z dowolnej formy typu suma iloczynów. Zaproponowana w artykule metoda została zilustrowana licznymi przykładami.
2
Content available Quality of Minimal Sets of Prime Implicants of Boolean Functions
Prasad V. C.
International Journal of Electronics and Telecommunications
|
2017
|
Vol. 63, No. 2
165--169
EN
Two new problems are posed and solved concerning minimal sets of prime implicants of Boolean functions. It is well known that the prime implicant set of a Boolean function should be minimal and have as few literals as possible. But it is not well known that min term repetitions should also be as few as possible to reduce power consumption. Determination of minimal sets of prime implicants is a well known problem. But nothing is known on the least number of (i) prime implicants (ii) literals and (iii) min term repetitions , any minimal set of prime implicants will have. These measures are useful to assess the quality of a minimal set. They are then extended to determine least number of prime implicants / implicates required to design a static hazard free circuit. The new technique tends to give smallest set of prime implicants for various objectives.
3
Content available remote It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton
Bojańczyk M.
Fundamenta Informaticae
|
2017
|
Vol. 154, nr 1/4
37--46
EN
The following problem is shown undecidable: given regular languages L, K of finite trees, decide if there exists a deterministic tree-walking automaton which accepts all trees in L and rejects all trees in K. The proof uses a technique of Kopczyński from [1].
4
Content available Boolean model of HSUH leakage testing for the purpose of designing a diagnosing unit of selected damages of vehicle braking mechanisms
Idzikowski A.
Archiwum Motoryzacji
|
2017
|
Vol. 78, nr 4
79--92
EN
The technical condition of the braking system of a vehicle admitted to traffic on public roads cannot raise any objections. Regardless of the intended use and structural solution, the braking systems can be divided into braking mechanisms and mechanisms and systems activating braking. The technical diagnostics include the assessment of technical suitability of the mechanisms activating braking and the determination of the braking system's performance at the test and measurement stand. For a diagnostician who checks the technical condition of a vehicle, this is a basic check in the field of road use safety. One of the symptoms of the technical failure of the vehicle braking system is the lack of tightness of the hydraulic circuit. In the process of exploitation, taking into account the safety of technical facilities, the factor that influences the development of diagnostics involves primarily the minimization of threats to human health and life, threats to the biological and technical environment. Guided by these assumptions, the purpose of the conducted research was to develop a method for diagnosing leakage of the hydraulic circuit for the needs of designing a braking system diagnosing unit. The publication presents the original mathematical model based on Boolean functions, which is a part of the mathematical analyses.
PL
Stan techniczny układu hamulcowego pojazdu dopuszczonego do ruchu na drogach publicznych nie może budzić zastrzeżeń. Niezależnie od przeznaczenia i rozwiązania konstrukcyjnego układy hamulcowe można podzielić na mechanizmy hamulcowe i mechanizmy oraz systemy uruchamiające hamulce. Diagnostyka techniczna obejmuje ocenę zdatności technicznej mechanizmów uruchamiających hamulce oraz określanie skuteczności działania układu hamulcowego na stanowisku badawczo-pomiarowym. Dla diagnosty, dokonującego sprawdzenia stanu technicznego pojazdu, jest to zasadnicze badanie kontrolne w zakresie bezpieczeństwa użytkowania pojazdu w ruchu drogowym. Jednym z symptomów niezdatności technicznej samochodowego układu hamulcowego jest brak szczelności obwodu hydraulicznego. W procesie eksploatacji mając na uwadze bezpieczeństwo obiektów technicznych czynnikiem wpływającym na rozwój diagnostyki jest przede wszystkim minimalizacja zagrożeń zdrowia i życia ludzkiego, zagrożeń środowiska biologicznego i technicznego. Kierując się tymi założeniami celem przeprowadzonych badań było opracowanie metody procesu diagnozowania nieszczelności obiegu hydraulicznego na potrzeby zaprojektowania diagnozera mechanizmów hamulcowych. W publikacji przedstawiono Autorski model matematyczny oparty na funkcjach boole’owskich, będący częścią prowadzonych analiz matematycznych.
5
Content available remote An Analysis of the C Class of Bent Functions
Mandal B., Gangopadhyay S., Stănică P., Pasalic E.
Fundamenta Informaticae
|
2016
|
Vol. 146, nr 3
271--292
EN
Two (so-called C;D) classes of permutation-based bent Boolean functions were introduced by Carlet [4] two decades ago, but without specifying some explicit construction methods for their construction (apart from the subclass D0). In this article, we look in more detail at the C class, and derive some existence and nonexistence results concerning the bent functions in the C class for many of the known classes of permutations over F2n. Most importantly, the existence results induce generic methods of constructing bent functions in class C which possibly do not belong to the completed Maiorana-McFarland class. The question whether the specific permutations and related subspaces we identify in this article indeed give bent functions outside the completed Maiorana-McFarland class remains open.
6
Content available remote On Language Equations with One-sided Concatenation
Baader F., Okhotin A.
Fundamenta Informaticae
|
2013
|
Vol. 126, nr 1
1--35
EN
Language equations are equations where both the constants occurring in the equations and the solutions are formal languages. They have first been introduced in formal language theory, but are now also considered in other areas of computer science. In the present paper, we restrict the attention to language equations with one-sided concatenation, but in contrast to previous work on these equations, we allow not just union but all Boolean operations to be used when formulating them. In addition, we are not just interested in deciding solvability of such equations, but also in deciding other properties of the set of solutions, like its cardinality (finite, infinite, uncountable) and whether it contains least/greatest solutions. We show that all these decision problems are EXPTIME-complete.
7
Content available Synthesis of Generalised Threshold Gates and Multi Threshold Threshold Gates
Nikodem M., Bawiec M. A., Biernat J.
International Journal of Electronics and Telecommunications
|
2012
|
Vol, 58, No. 1
49-54
EN
This paper presents synthesis algorithms for Generalised and Multi Threshold Threshold Gates. Both algorithms can be applied to generate circuit structures for arbitrary Boolean functions. We present gate's formal models, synthesis algorithms and complexity estimations of the resulting structures.
8
Content available Symetryczne względem cyklicznego przesunięcia argumentów funkcje boolowskie o nieparzystej liczbie zmiennych
Kijko T.
Biuletyn Wojskowej Akademii Technicznej
|
2008
|
Vol. 57, nr 4
151-166
PL
Artykuł zawiera opis strategii znajdowania symetrycznych względem cyklicznego przesunięcia argumentów funkcji boolowskich o okrelonych własnościach kryptogracznych. Zawiera on także podstawowe definicje i twierdzenia dotyczące funkcji boolowskich i najistotniejszych parametrów kryptograficznych. Dodatkowo przedstawione zostały wyniki zastosowania opisanej strategii do znajdowania funkcji o parametrach (9, 3, 5, 240).
EN
This paper contains description of search strategy for rotation symmetric Boolean functions with certain cryptographic properties. There are also presented basic definitions and theorems connected to Boolean functions and the most important cryptographic parameters of the functions. Additionaly the practical results for searching for functions with parameters (9, 3, 5, 240) are given.
9
Content available remote Nonlinearity of the round function
Kontak M., Szmidt J.
Control and Cybernetics
|
2007
|
Vol. 36, no 4
1037-1044
EN
In the paper we present the results which enable to calculate the nonlinearity of the round function with quite large dimensions, e.g. 32 x 32 bits, which are used in some block ciphers. It can be used to estimate resistance of these ciphers against linear cryptanalysis. We give the application to linear cryptanalysis of the TGR block cipher.
10
Content available Random generation of Boolean functions with high degree of correlation immunity
Grocholewska-Czuryło A.
Journal of Telecommunications and Information Technology
|
2006
|
nr 3
14-18
EN
In recent years a cryptographic community is paying a lot of attention to the constructions of so called resilient functions for use mainly in stream cipher systems. Very little work however has been devoted to random generation of such functions. This paper tries to fill that gap and presents an algorithm that can generate at random highly nonlinear resilient functions. Generated functions are analyzed and compared to the results obtained from the best know constructions and some upper bounds on nonlinearity and resiliency. It is shown that randomly generated functions achieve in most cases results equal to the best known designs, while in other cases fall just behind such constructs. It is argued that the algorithm can perhaps be used to prove the existence of some resilient functions for which no mathematical prove has been given so far.
11
Content available remote Heuristics for Thelen's Prime Implicant Method
Bieganowski J., Karatkevich A.
Schedae Informaticae
|
2005
|
Vol. 14
125-135
EN
Thelen's algorithm is an efficient method for generation of the prime implicants of a Boolean function represented in CNF. In the paper new heuristics are presented, allowing to accelerate the algorithm. Experimental analysis of their effects is performed.
12
The Three-Yalued Sign Walsh Coefficients Calculation for an Affine Boolean Function Recognition
Porwik P.
Archiwum Informatyki Teoretycznej i Stosowanej
|
2005
|
T. 17, z. 3
199-211
EN
The paper discusses a problem of recognition of the Boolean function linearity. The linearity of function is investigated by means of the threevalued sign Walsh coefficients. The linearity and nonlinearity play an important role in many domains especially in designing of digital circuits. The knowledge about spectral coefflcients distribution allows to determine the various combinatorial properties of the Boolean functions: redundancy, monotonicity, self-duality, correcting capability, etc., which seems to be more difficult in realization by means of others methods. Experimental results demonstrate the efficiency of the approach.
PL
W pracy przedstawiono metodę rozpoznawania afmicznej funkcji boolowskiej na podstawie analizy jej trójwartościowego, znakowego widma Walsha. Boolowskie funkcje liniowe (afmiczne) są ważną klasą funkcji wykorzystywaną w kryptografii, projektowaniu układów arytmetycznych i kodów kontrolnych. Ze względu na ważność zagadnienia, metody znajdowania lub rozpoznawania takich funkcji są ciągle przedmiotem badań i udoskonaleń. Wykazano, że dla celów rozpoznawania w pełni określonych funkcji afinicznych klasyczną transformację Walsha-Hadamarda można uprościć i zrealizować w wersji znakowej, co ogranicza zakres dopuszczalnych wartości widma. W pracy wykazano, że widmo wyznaczone dla funkcji zapisanej w postaci ON-sześcianów (ang. cubes) może zostać również uproszczone. Zaproponowano trójwartościową reprezentację widma, gdzie używane są tylko trzy znaki (symbole) {+1, -1,0},co zmniejsza liczbę bitów niezbędnych do przechowywania wartości widma. Wyznaczono złożoność obliczeniową (O) oraz pamięciową (M) w bajtach obu przedstawionych w pracy metod. Wartości te wynoszą odpowiednio: dla znakowej transformacji Walsha-Hadamarda: O(2n) oraz M(2n+2), natomiast dla znakowej transformacji wykorzystującej zapis w postaci sześcianów O(n2 2n) oraz M(2n-2).
13
Content available Boolean feedback functions for full-length nonlinear shift registers
Janicka-Lipska I., Stokłosa J.
Journal of Telecommunications and Information Technology
|
2004
|
nr 4
28-30
EN
In the paper a heuristic algorithm for a random generation of feedback functions for Boolean full-length shift register sequences is presented. With the help of the algorithm one can generate n-stage Boolean full-length shift register sequences for (potentially) arbitrary n ? 6. Some properties of the generated feedback functions are presented.
14
Towards calculation of boolean functions nonlinearity using Walsh transform
Porwik P.
Archiwum Informatyki Teoretycznej i Stosowanej
|
2000
|
T. 12, z. 1
51-64
EN
The estimation of nonlinearity function has wide applications in cryptography, transmission of information, correction of erros, etc. Linearity and nonlinearity plays important role in designing of digital circuits too - particularly in build of Boolean functions through spectral decomposition. This work presents a method to evaluate linearity and nonlinearity by analysis of spectral coefficients. The nonlinearity can be expressed in terms of Walsh spectra of Boolean functions. In this paper relation between linear Boolean functions and their Walsh spectra is presented. Analysis of the coefficients' distribution allows determining various combinatorial properties of the Boolean functions: redundancy, monotonicity or linearity for example, what seems to be more difficult to execute by means of other methods. Additionaly the Walsh-Hadamard transform allows us to accelerate the computer calculates, particularly for very large Boolean functions (of many variables) and to reduce the cost of correlation computations.
PL
W pracy przedstawiono metodę wyznaczania liniowości i nieliniowości funkcji boolowskiej za pomocą transformacji Walsha. Koncepcja zaproponowanego rozwiązania polega na obliczaniu współczynników korelacji R lub S pomiędzy badaną funkcją boolowską i odpowiednią podstawową lub rozszerzoną dyskretną funkcją Walsha. Stosując znany algorytm szybkiej transformacji Walsha, można zredukować złożoność wyznaczania nieliniowości do n2n operacji dodawań. Jednokrotne obliczenie współczynników (widma) ze zbioru R lub S jest równoznaczne ze znajomością współczynników liniowości/nieliniowości badanej funkcji boolowskiej w stosunku do wszystkich innych możliwych funkcji liniowych o tym samym rozmiarze. Metoda może być stosowana podczas weryfikacji projektów układów cyfrowych oraz w kryptografii.
15
Content available remote Własności informatyczne transformaty Walsha
Porwik P., Słota D.
Kwartalnik Elektroniki i Telekomunikacji
|
1999
|
Vol. 45, nr 3-4
287-293
PL
W artykule omówiono nowe możliwości interpretacji współczynników widmowych funkcji boolowskich rozłożonych w dyskretny szereg Walsha. Stosując analizę współczynników można przeprowadzić pewna ogólną, dotychczas nigdzie nie opisaną klasyfikację funkcji boolowskich i szacować pewne ich właściwości. W pracy przedstawiono także w nowym świetle własności samej transformacji opartej na funkcjach Walsha. Na podstawie własności transformaty Walsha można uprościć interpretację współczynników lub na ich podstawie określić właściwości kombinacyjnych funkcji boolowskich na przykład redundancję lub liniowość co wydaje się być trudniejsze do wykonania za pomocą innych, klasycznych metod.
EN
This paper presents the short background about Boolean functions and their relation to Walsh - Hadamard transform. This transform reduces the costs of correlation computations. In this paper has been considered a new method of interpretation of Boolean function spectrum. The analysis methods described in this paper may be generalised to many - valued logical functions. By means of spectrum analysis we obtain information about properties of Boolean functions. For some classes of Boolean functions we can investigate the redundancy by spectrum coefficients analysis only. We have presented discussion of some theorems, which has played important role in analysis of Boolean functions. The presented result can be used in testing and very often plays important role in building of logical functions.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.